2022 KAKAO BLIND RECRUITMENT - 양궁대회

Java

2022 KAKAO BLIND RECRUITMENT - 양궁대회

문제

문제 출처

접근 방법

문제에서 주어진 내용은 피치가 총 n발의 화살을 쏘았을 때, 라이언이 n발의 화살을 쏘아 가장 큰 격차의 점수 차를 내는 것이다.

DFS를 사용하여 라이언이 n개의 화살을 쏴 과녁의 점수에 맞출 수 있는 모든 경우의 수를 파악한다.
여기서 주의해야할 점은 문제에서 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요. 라고 되어있다.
따라서 0점부터 라이언이 n발을 맞춘 것을 시작으로 10점에 n발을 맞춘 것 까지 순서대로 조합의 결과를 구한다.
이를 사용하면 가장 격차가 큰 화살들의 정보가 처음 등장할 때가 가장 낮은 점수를 더 많이 맞힌 경우가 된다.

DFS를 사용하여 총 n발의 화살을 맞추었을 조합이 만들어 졌을 때, 피치의 점수와 비교하여 가장 큰 격차의 점수를 구하고 그에 따른 라이언이 우승하기 위한 경우를 구한다.

코드

import java.util.*;

class Solution {
	static int N, maxScore = -1;
	static int[] sel, INFO;
	static int[] result;
	public static int[] solution(int n, int[] info) {
		N = n;
        int[] answer = {};
        INFO = info.clone();
        sel = new int[11];		// 라이언이 과녁에 쏜 화살의 정보들
        result = new int[] {-1};

        DFS(10,0);

        answer = result.clone();
        return answer;
    }
	// lv은 현재 라이언이 몇 점짜리 점수를 쏘는지, 시작은 0점 마지막은 10점
	static void DFS(int lv, int sum) {
		if(lv == -1 || sum == N) {
			if(sum == N) {
				//System.out.println(Arrays.toString(sel));
				int diff = calScore();

				if(diff > maxScore) {
					result = sel.clone();
					maxScore = diff;
				}
				return;
			}
			return;
		}

		// 현재 점수칸에 몇개의 화살을 쏠 건지
		for(int i = N - sum; i >= 0; i--) {
			sel[lv] = i;
			DFS(lv - 1, sum + i);
		}
	}

	static int calScore() {
		int rion = 0, peach = 0;

		for(int i = 0; i <= 10; i++) {
			// 어피치의 맞춘 화살이 같거나 더 클 때
			if(INFO[i] >= sel[i] && INFO[i] != 0) {
				peach += (10 - i);
			}
			else if(sel[i] > INFO[i] && sel[i] != 0) {
				rion += (10 - i);
			}
		}
		// 무조건 라이언이 이겼을 때
		if(rion - peach > 0) {
			return rion - peach;
		}
		return -1;
	}

    public static void main(String[] args) {
    	int[] arr = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 3, 4, 3};
    	System.out.println(Arrays.toString(solution(10, arr)));
	}
}

후기 및 개선할 점