[프로그래머스: JAVA] 양궁대회

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

---

[1회차] 11월 11일, 문제 추천받음

문제 접근 방법 (사용 자료구조, 알고리즘)

 

일단 스토리라인을 적어보자면 다음과 같다

 

라이언이 이겨야 함, 라이언이 못 이기는 경우는 -1 출력

이기려면 ? 총합 점수가 많아야 해 -> 점수 어떻게 내는데?

k 점을 어피지랑 똑같은 갯수로 맞추면 점수는 어피치꺼

k 점을 어피치보다 많이 맞추면 점수는 라이언꺼

k 점을 둘 다 못 맞추면 0점

 

-- 일단 점수를 낼 수 있게 코딩을 해보자

어피치 점수는 상대적임, 라이언이 어떻게 쏘냐에 따라 달렸음

사실상 각 k 점에서 점수를 어떻게 내느냐에 따라 달렸음

점수 낼꺼냐 // 점수 안 낼꺼냐 // 점수 줄거냐

 

-- 엥 DFS 가능할까요? - 가능할지도 - 가능하다

로직(DFS)
(0) [베이스케이스] 탐색해야 할 점수판 번호(depth)가 11에 닿았을 때, 두 가지를 확인한다.
  - 화살을 다 썼는가
  - 라이언이 어피치보다 점수를 많이 내었느냐
    위 두 가지 조건문을 거치면 최대 점수의 배열을 갱신하고 최대 점수와 같을 경우 문제 조건에 맞게 처리한다.
[처리문] : 재귀조건
(1) 점수를 안 낼꺼냐 : 둘 다 0 일 경우(일단 어피치가 0 점이어야 가능성이라도 있기 때문)
(2) 점수를 낼 경우 : 어피치보다 무조건 많이 쏴야 함, 근데 점수 차이가 많이 날려면 1개만 차이나야 화살을 아낄 수 잇음
(3) 점수를 줄 경우 : 어피치와 똑같은수의 화살을 쏘거나 어피치보다 적게 쏘거나의 경우의 수

 

 

메모리 & 시간

프로그래머스는 확인이 불가함, 제공하지 않고 있음 

 

 

 

코드

class Solution {
        static int[] r, a, ans;
        static boolean isFind;
        static int max;

        public static int[] solution(int n, int[] info) {
            a = info.clone();
            r = new int[11];

            max = Integer.MIN_VALUE;
            ans = new int[11];
            isFind = false;
            shoot(0, n, 0, 0);

            return isFind == true? ans: new int[] {-1};
        }

    private static void shoot(int depth, int rest, int apeach, int ryan) {
        if(depth == 11) {
            if(rest == 0 && ryan > apeach) {
                isFind = true;
                if(max < (ryan - apeach)) {
                    max = ryan - apeach;
                    ans = r.clone();
                } else if(max == (ryan - apeach)) {
                    // 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
                    for (int i = 10; i >= 0; i--) {
                        if(r[i] > ans[i]) {
                            ans = r.clone();
                            return;
                        } else if(r[i] < ans[i]) return;
                    }
                }
            }
            return;
        }


        // 점수를 안 낼꺼냐 : 둘 다 0 일 경우 : 일단 어피치가 0 점이어야 가능성이라도 있음 
        if(a[depth] == 0) {
            shoot(depth + 1, rest, apeach, ryan);
        } 

        // 점수를 낼 경우 : 어피치보다 무조건 많이 쏴야 함, 근데 점수 차이가 많이 날려면 1개만 차이나야 화살을 아낄 수 잇음
        if(rest > a[depth]) {
            r[depth] = a[depth] + 1;
            shoot(depth + 1, rest - a[depth] - 1, apeach, ryan + (10 - depth));
            r[depth] = 0;
        }

        // 점수를 줄 경우 : 어피치와 똑같은수의 화살을 쏘거나 어피치보다 적게 쏘거나의 경우의 수
        if(a[depth] != 0) {
            for (int i = 0; i < a[depth]; i++) {
                if(rest >= i) {
                    r[depth] = i;
                    shoot(depth + 1, rest - i, apeach + (10 - depth), ryan);
                    r[depth] = 0;
                }
            }
        }
    }
	}

 

 

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
10분	10분	40분