Kakao 2022 Blind Test - Lv2. 양궁대회 (Java)

문제 요약

양궁대회에서 라이언이 우승할 수 있는 방법들 중 가장 낮은 점수를 더 많이 맞힌 경우를 찾아 return,
없다면 [-1] return

 

[문제 설명 및 제한 조건] 

• 어피치와 라이언이 양궁대회 결승전에 올라왔다.
• 다양한 선수가 양궁대회에서 우승할 수 있도록 하기 위해, 운영위원회는 라이언에게 불리하도록 결승전 규칙을 정하였다.
  • k점에 여러발을 맞추었더라도, k점만 획득할 수 있다.
  • k점을 어피치가 a발, 라이언이 b발을 맞췄을 경우, a >= b 일 경우에 어피치가 k 점을 획득한다.

 

[입출력]

1. n: 각 양궁 선수가 화살을 쏠 수 있는 총 개수 (1 ≤ n ≤ 10)
2. info: 어피치가 쏜 화살의 정보 (0 ≤ info의 원소 ≤ n, info의 원소 총합 = n) 
3. 라이언이 어피치를 이길 수 없는 경우에는 [-1] return
4. 라이언이 어피치를 이길 수 있다면 이길 수 있는 경우 중, 가장 낮은 점수를 더 많이 맞힌 경우 return

n	info	result
5	[2,1,1,1,0,0,0,0,0,0,0]	[0,2,2,0,1,0,0,0,0,0,0]

• info의 i 번째 원소는 과녁의 10-i 점을 맞힌 화살의 개수
• 즉, 0번째 원소의 점수는 10점
• 1번째 원소의 점수는 9점

---

문제 접근 

• 깊이우선탐색(dfs)와 백트래킹을 이용하여 문제를 풀었습니다. 
• 높은 점수부터 라이언이 쏜 화살의 개수를 탐색하기 때문에, 라이언이 가장 큰 점수차이로 우승할 수 있는 방법 중 가장 낮은 점수를 더 많이 맞힌 경우가 최종 return 됩니다. 

자세한 접근 법은 코드의 주석을 확인하세요 🙂

 

// 22. 06. 11. 토 - 2022 카카오 블라인드 - Lv.2 - 양궁대회

public class Solution {
    public static void main(String[] args) {
        solution(5, new int[]{2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0});
    }

    public static int[] solution(int n, int[] info) {
        int[] answer = {};
        dfs(0, n, new int[11], info);
        answer = min_array;
        return answer;
    }


    static int[] min_array = {-1}; // 라이언이 쏜 화살의 합 중 라이언의 점수가 어피치 점수보다 낮거나 같으면 [-1]
    static int max_score = Integer.MIN_VALUE; // 라이언이 쏜 화살의 합 중 어피치 점수보다 높을 경우에만 갱신

    /**
     * 라이언이 어피치가 쏜 화살만큼 화살을 쏘고, 어피치보다 점수가 높은 경우들 중 가장 낮은 점수를 더 많이 맞힌 경우를 찾아낸다.
     *
     * @param level: 라이언이 쏜 화살의 개수
     * @param n: 어피치가 쏜 화살의 총 개수
     * @param scores: 라이언이 쏜 화살 정보를 보관하는 배열
     * @param info: 어피치가 쏜 화살 정보를 보관하는 배열
     */
    private static void dfs(int level, int n, int[] scores, int[] info) {
        if (level == n) {
            int total_score = 0; // 라이언이 획득한 총 점수
            int opposite_score = 0; // 어피치가 획득한 총 점수

            for (int i = 0; i <= 10; i++) {
                if (scores[i] > 0 || info[i] > 0) {
                    if (scores[i] > info[i]) total_score += 10 - i;
                    else opposite_score += 10 - i;
                }
            }

            // 라이언이 어피치보다 점수르 많이 획득했을 때 이길 수 있다.
            // 라이언이 어피치를 이기는 경우 중 점수 차이가 크게 나는 경우를 찾는다.
            // 라이언이 어피치를 이기는 경우 중 점수 차이가 동점일 경우, 더 낮은 점수를 많이 맞히는 경우를 찾는다.
            if (total_score > opposite_score && total_score - opposite_score >= max_score) {
                // 가장 낮은 점수를 더 많이 맞힌 경우를 min_array에 넣기
                max_score = total_score - opposite_score;
                min_array = scores.clone();
            }
            return;
        }

        for (int i = 0; i <= 10; i++) {
            // 라이언이 어피치를 이기기 위해서 같은 점수대에서 어피치보다 1발 더 많이 맞추면 되는 것이지
            // 2발 이상 더 많이 맞춘 경우를 살펴볼 필요는 없다.
            // 즉, 각 점수대에서 어피치보다 1발 더 많이 맞추어 점수를 획득하고
            // 나머지 남은 횟수는 다른 점수대를 공략하는 것이 더 높은 점수를 획득하는 방법이다.
            if(scores[i] > info[i]) break;

            scores[i]++;
            dfs(level + 1, n, scores, info);
            scores[i]--;
        }
    }
}

---

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/92342

코딩테스트 연습 - 양궁대회