[2022 카카오 블라인드]양궁 대회★

📍 문제 설명

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

프로그래머스

 

💡 접근

x발을 모든 과녁에 맞춰보고 점수를 계산해봐야 한다.

단, 뻗어나가는 과정에서 어피치와 같은 과녁수일 때 까지만 루프를 돌려서 라이언이 +1발만 쐈을 때 점수를 얻을 수 있게 해야 한다.

 

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int m, max;
    static int[] apeach, lion = new int[11], result = {-1};

    public int[] solution(int n, int[] info) {
        m = n;
        apeach = info;
        dfs(0);
        return result;
    }

    public void dfs(int L) {
        if(L == m) {
            int apeach_score = 0, lion_score = 0;
            //최종 점수 계산
            for(int i = 0; i < 11; i++) {
                //둘 중 한명은 쏴야 점수로 인정
                if(apeach[i] != 0 || lion[i] != 0) {
                    if(apeach[i] < lion[i]) lion_score += 10 - i;
                    else apeach_score += 10 - i;
                }
            }
            //라이언이 이긴 경우와 기존의 점수보다 큰 경우에 갱신
            if(lion_score > apeach_score && lion_score - apeach_score >= max) {
                result = lion.clone();
                max = lion_score - apeach_score;
            }
        }
        else {
            //x 발을 모든 과녁(11개의 과녁)에 맞춰보고 점수 계산하기
            //어피치가 쏜 과녁보다 적게 쐈거나 같게 쐈을 경우에만 탐색
            for(int i = 0; i < 11 && lion[i] <= apeach[i]; i++) {
                lion[i]++;
                dfs(L+1);
                lion[i]--;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main t = new Main();
        int n = 5;
        int[] info = {2,1,1,1,0,0,0,0,0,0,0};
        t.solution(n, info);
    }
}