[2022 Kakao blind recruitment] 양궁대회

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

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

[초기코드]

틀렸던 원인 : 

라이언이 어피치를 이겼을 때 가질 수 있는 최대 점수를 구하려고 했다.

하지만 문제를 잘 읽어보니 최대 점수가 아닌 어피치를 이길경우의 어피치점수와의 최대 격차를 구하는 문제였다.

 

또한, 같은 격차로 이기는 케이스가 여러개일 경우, 더 낮은 점수를 많이 맞추는 경우를 리턴했어야 했는데 이 부분 로직이 잘못되었었다.

#include <string>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;
int apeach[11];
int max_score = -1;
int board[11];
int lion[11];

void dfs(int idx, int cnt, int n) {
    if(cnt == n) {
        int lion_score = 0;
        int apeach_score = 0;
        for(int i=0; i<11; i++) {
            if(apeach[i] == 0 && lion[i]== 0) continue;
            if(apeach[i] < lion[i] && lion[i] != 0)
                lion_score += (10-i);
            else if(apeach[i] > 0)
                apeach_score += (10-i);
        }
       
        if(lion_score <= apeach_score) return;
      
        if(lion_score > max_score) {
            max_score = lion_score;
            for(int i=0; i<11; i++) {
                board[i] = lion[i];
            }
        }
        else if(lion_score == max_score) {
            bool exchage = false;
            for(int i=10; i>=0; i--) {
                if(lion[i] > board[i]) {
                    exchage = true;
                    break;
                }
            }
            if(exchage) {
                for(int i=0; i<11; i++)
                    board[i] = lion[i];
            }
        }
        return;
    }
    
    for(int i=idx; i<11; i++) {
        lion[i]++;
        dfs(i, cnt+1, n);
        lion[i]--;
    }
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
        
    int target = 0;
    for(int i=0; i<11; i++) {
        apeach[i] = info[i];
    }
    
    dfs(0, 0, n);
    
    if(max_score == -1) {
        answer.push_back(-1);
        return answer;
    }
    
    for(int i=0; i<11; i++)
        answer.push_back(board[i]);
    
    return answer;
}

[풀이방법]

1. 라이언이 쏠 수 있는 모든 경우를 구한다. n뽑기 중복조합 (효율성이 좀 문제가 될거 같긴했지만 일단 했음.)

2. 각 경우에서 나오는 어피치의 점수와 라이언의 점수를 구한다.

3. 라이언이 이기는 경우인지 확인한다.

4. 라이언이 이긴다면 라이언과 어피치의 점수의 격차가 지금까지 구한 최대격차보다 크거나 같은지 확인한다.

5-1. 크다면 케이스를 board 에 업데이트하고, 최대격차 또한 업데이트 해준다.

5-2.같다면 board 와 현재 케이스를 비교해서 현재 케이스가 board보다 작은 점수의 표적에 화살을 많이 쐈는지 확인한다. 더 많이 쐈다면 board 를 현재 케이스로 업데이트한다.

6. board 를 answer 에 옮겨 리턴해준다.

 

문제가 될 수 있을 것 같다고 생각한 부분은 1번이었는데, 이 문제의 경우 효율성 테스트가 없어서 통과를 했던 것 같다. 만약 효율성 테스트가 있고, 표적이 더 크거나 화살이 많아서 경우의 수가 더 많았더라면 통과하지 못했을 것 같다.

다른 사람들의 코드를 참고해본 결과, dfs 재귀를 돌리기 전에 아래 경우를 체크하여 재귀를 필터링 하는 것을 볼 수 있었다.

 

남은 화살의 갯수가 (현재 표적에 어피치가 쏜 화살의 갯수+1)보다 적을 경우, 이 표적에 쏘지 않는다.

라이언에게 남은 화살이 2개일 경우, 6점 표적에 어피치가 이미 3개의 화살을 맞췄을 경우 라이언은 남은 화살 두개를 다 6점 표적에 쏜다고 해도 점수를 얻을 수가 없다. 따라서 이 표적에는 쏘지 않는것이 이득이다.

 

경우체크를 하지 않았는데도 통과를 했다. 다시 한번, 문제 잘 읽자...ㅎ

 

[최종 코드]

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int apeach[11];
int max_score = -1;
int board[11];
int lion[11];

void dfs(int idx, int cnt, int n) {
    if(cnt == n) {
        int lion_score = 0;
        int apeach_score = 0;
        for(int i=0; i<11; i++) {
            if(apeach[i] == 0 && lion[i]== 0) continue;
            if(apeach[i] < lion[i] && lion[i] != 0)
                lion_score += (10-i);
            else if(apeach[i] > 0)
                apeach_score += (10-i);
        }
        if(lion_score <= apeach_score) return;
      
        if((lion_score-apeach_score) > max_score) {
            max_score = (lion_score-apeach_score);
            for(int i=0; i<11; i++) {
                board[i] = lion[i];
            }
        }
        else if((lion_score-apeach_score) == max_score) {
            bool exchage = false;
            for(int i=10; i>=0; i--) {
                if(lion[i] > board[i]) {
                    exchage = true;
                    break;
                }
                else if(board[i] > lion[i]) {
                    break;
                }
            }
            if(exchage) {
                for(int i=0; i<11; i++)
                    board[i] = lion[i];
            }
        }
        return;
    }
    
    for(int i=idx; i<11; i++) {
        lion[i]++;
        dfs(i, cnt+1, n);
        lion[i]--;
    }
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
        
    int target = 0;
    for(int i=0; i<11; i++) {
        apeach[i] = info[i];
    }
    
    dfs(0, 0, n);
    
    if(max_score == -1) {
        answer.push_back(-1);
        return answer;
    }
    
    for(int i=0; i<11; i++)
        answer.push_back(board[i]);
    
    return answer;
}