참고
문제해설
문제 로직고민
NOTE
•
로직에 대한 발상은 DFS로 바로 생각났는데, 구현과 정확도를 맞추는데서 오래걸렸다.
◦
2^10의 경우이므로 완전탐색을 통해 구하려고 진행
◦
문제가 상당히 길어서 대충읽고 넘어갔는데 핵심적인 요소를 놓쳤었다
▪
라이언의 최대점수가 아닌, 라이언과 어피치의 최대 점수차이를 구해야한다.
▪
점수가 동일하면 낮은 점수에 화살을 많이 투자한쪽으로 수정해야한다.
◦
사실 이거 2개 놓쳐서 1시간은 더 쓴거같다…
작성코드
NOTE
class Solution {
int max = 0;
int[] answer = {-1};
int[] win_cnt;
boolean[] apeach_shot;
int[] lion_shot;
public int[] solution(int n, int[] info) {
win_cnt = new int[info.length];
apeach_shot = new boolean[info.length];
lion_shot = new int[info.length];
for(int i=0; i<win_cnt.length; i++){
if(info[i] > 0) apeach_shot[i] = true;
win_cnt[i] = info[i] + 1;
}
dfs(0, n);
return answer;
}
private void dfs(int cnt, int rest){
if(cnt == 11 || rest == 0){
lion_shot[10] += rest;
int apeach = 0;
int lion = 0;
// 점수비교
for(int i=0; i<11; i++){
int score = 10-i;
if(lion_shot[i] > 0) lion += score;
else if(lion_shot[i] == 0 && apeach_shot[i]) apeach += score;
}
// 최대점수 갱신
if(lion > apeach && lion-apeach >= max) {
System.out.println();
if(lion-apeach != max || isBetter()){
answer = new int[11];
max = lion-apeach;
System.arraycopy(lion_shot, 0, answer, 0, lion_shot.length);
}
}
lion_shot[10] -= rest;
return;
}
// 점수를 얻는다.
if(rest >= win_cnt[cnt]){
lion_shot[cnt] += win_cnt[cnt];
dfs(cnt+1, rest - win_cnt[cnt]);
lion_shot[cnt] -= win_cnt[cnt];
}
// 점수를 포기한다
dfs(cnt+1, rest);
}
private boolean isBetter(){
for(int i=10; i>=0; i--){
if(answer[i] > lion_shot[i]) return false;
else if(answer[i] < lion_shot[i]) return true;
}
return false;
}
}
Java
복사
다른사람 풀이
NOTE
class Solution {
int max, ans[], apeach[];
void find(int n, int cur) {
int score = 0, state[] = new int[11];
for(int i=1; i<=10; i++) {
if((cur&1<<i) > 0) {
n -= state[10-i] = apeach[10-i]+1;
if(n < 0) return;
score += i;
}else if(apeach[10-i] > 0) score -= i;
}
if(score <= 0) return;
state[10] = n;
if(max < score) {
max = score;
ans = state;
}else if(max == score) {
for(int i=10; i>=0; i--) {
if(ans[i] != state[i]) {
if(state[i] > ans[i])
ans = state;
return;
}
}
}
}
int[] solution(int n, int[] info) {
apeach = info;
for(int i=1; i<1<<11; i++)
if(Integer.bitCount(i) <= n)
find(n, i);
return max == 0 ? new int[] {-1} : ans;
}
}
Java
복사
깔-끔 코드