문제

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

---

입력

• 화살의 개수를 담은 자연수 n
• 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info

---

출력

• 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return

---

풀이

제한조건

• 1 ≤ n ≤ 10
• info의 길이 = 11
• 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
• 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.

접근방법

순열 응용

N과 info의 길이가 크지 않다. 따라서 완전탐색을 고려해볼만하다.
또한 제한 조건 중 라이언이 어떻게 화살을 쏘든 라이언의 점수가 어피치의 점수보다 낮거나 같으면 [-1]을 return 해야 합니다.라는 조건을 조금 다르게 해석 해보자면, 완전 탐색으로도 못 구하면 -1을 반환하라 라는 의미이다.

그리디 유형의 문제라면 어떻게 화살을 쏘든이라는 완전 탐색을 암시하는 듯한 문구가 없을 것이다.

이제 문제를 읽으며 정리해보자

1. 가장 큰 점수 차이로 우승할 것.
2. 점수 차이가 같다면, 낮은 점수를 더 많이 쏜 것.
3. 반드시 N발을 모두 쏠 것.
4. 구할 수 없다면 -1
5. 점수계산식 주의

문제의 조건이 많다.
빼먹지 말고 처음부터 잘 정리해서 기록하자.

1. 순열을 뒤에서부터
2. 큰 수부터
   생성했다.

즉 일반적인 순열을 생성하면

00005 -- 정답후보1
00014
00023
00032
00041
00104 -- 정답후보2 (두 번째로 낮은점수 많이 쏨)
.
.
.

순으로 생성하면, 조건1과 조건2를 만족하기 위해 추가적인 조건문을 작성해야한다.
하지만 반대로 생성한다면 자연스럽게 조건1과 조건2를 만족시키며 비교할 수 있다.

00005
00014
00104
01004
10004
00023
.
.
.

길이만큼의 순열이 생성되었다면, 점수비교를 해주면 끝이다.

순열을 생성하는 과정에서 화살을 몇 발 쏘았는지의 정보를 매개변수로 넘겨주며
N발 보다 많이 쏜 경우, 과감하게 return 시켜서 불필요한 순열 생성을 막아주자.
또한 순열이 완성되었을때, N발보다 적게 쏜 경우도 빠르게 걸러주자.

문제를 잘 읽자!

---

코드

import java.util.Arrays;

public class Solution {
	int[] apeach, ryan, answer;
	int N, maxScore;
	final int SIZE = 11;

	public int[] solution(int n, int[] info) {
		ryan = new int[SIZE];
		answer = new int[SIZE];
		N = n;
		apeach = info;
		maxScore = 0;
		perm(SIZE - 1, 0);

		if (maxScore == 0)
			return new int[] {-1};
		return answer;
	}

	private void perm(int depth, int sum) {
		if (sum > N)
			return;

		if (depth == -1) {
			// 화살을 모두 소비하지 않는 경우는 생략
			if (sum != N)
				return;

			int ryanScore = 0;
			int apeachScore = 0;
			for (int i = 0; i < SIZE; ++i) {
				// 같은 수를 맞힌경우
				if (ryan[i] == apeach[i]) {
					// 어피치가 0발이 아니라면, 점수를 얻는다.
					if (apeach[i] != 0)
						apeachScore += (10 - i);
				} else if (ryan[i] > apeach[i]) {
					ryanScore += (10 - i);
				} else {
					apeachScore += (10 - i);
				}
			}

			int diff = ryanScore - apeachScore;
			if (diff > maxScore) {
				maxScore = diff;
				answer = Arrays.copyOf(ryan, SIZE);
			}
			return;
		}

		for (int i = N; i >= 0; --i) {
			ryan[depth] = i;
			perm(depth - 1, sum + i);
		}
	}
}