Lv 2. 양궁대회

 

https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2%2C3%2C4&languages=java&page=7

코딩테스트 연습 | 프로그래머스 스쿨

 

 

 

📌 자바(Java)로 푸는 양궁대회 문제 풀이 🚀

---

🔎 문제 개요

이 문제는 프로그래머스 - 양궁대회 문제입니다.
라이언이 화살 n개를 사용하여 어피치보다 높은 점수를 얻는 방법을 찾아야 합니다.
단, 어피치의 화살 기록(info[])이 주어지며, 점수 차이가 가장 큰 경우를 선택해야 합니다.

---

💡 예제 입력

int n = 5;
int[] info = {2,1,1,1,0,0,0,0,0,0,0};

💡 예제 출력

[0,2,2,0,1,0,0,0,0,0,0]

라이언이 최적의 화살 배분을 했을 때,
어피치보다 높은 점수를 얻으면서 점수 차이가 가장 큰 경우를 반환해야 합니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 백트래킹(DFS) 알고리즘을 활용합니다.

✏️ 주요 고려 사항

✔ 각 점수 영역(0~10)에서 화살을 어떻게 분배할지 탐색
✔ 어피치보다 1개 더 많이 맞히는 경우 vs 그냥 지나치는 경우 선택
✔ 점수 차이가 가장 큰 경우를 선택
✔ 점수 차이가 같은 경우, 낮은 점수를 더 많이 맞힌 경우를 선택

---

🔹 Java 코드 해설

import java.util.*;

class Solution {

    int[] answer;    // 최적의 화살 배분 저장
    int[] now;       // 현재 화살 배분 상태
    int maximum = 0; // 최대 점수 차이
    int score = 0;   // 어피치 초기 점수
    boolean found = false; // 적절한 배분이 존재하는지 확인

    public int[] solution(int n, int[] info) {
        answer = new int[11];
        now = new int[11];

        // 어피치의 총 점수 계산
        for (int i = 0; i < 10; i++) {
            if (info[i] != 0)
                score += (10 - i);
        }

        // DFS 탐색 시작
        dfs(0, n, 0, score, info);

        // 최적의 화살 배분이 없는 경우
        if (!found)
            return new int[]{-1};

        return answer;
    }

    public void dfs(int depth, int count, int sum, int s, int[] info) {
        // 10번째 화살까지 모두 탐색했을 경우
        if (depth == 10) {
            now[10] = count; // 남은 화살을 모두 마지막 칸에 사용
            int diff = sum - s; // 점수 차이 계산

            // 최대 점수 차이 갱신
            if (diff > maximum) {
                maximum = diff;
                found = true;
                answer = now.clone(); // 최적의 화살 배분 저장
            } 
            // 점수 차이가 같을 경우, 낮은 점수를 더 많이 맞힌 경우를 선택
            else if (diff == maximum) {
                if (isBetter(now, answer))
                    answer = now.clone();
            }

            now[10] = 0; // 원상 복구
            return;
        }

        // 어피치보다 1개 더 맞혀서 점수를 가져가는 경우
        if (count >= info[depth] + 1) {
            now[depth] = info[depth] + 1;

            if (info[depth] > 0)
                dfs(depth + 1, count - (info[depth] + 1), sum + (10 - depth), s - (10 - depth), info);
            else
                dfs(depth + 1, count - (info[depth] + 1), sum + (10 - depth), s, info);

            now[depth] = 0; // 원상 복구
        }

        // 해당 점수를 포기하는 경우
        dfs(depth + 1, count, sum, s, info);
    }

    // 점수 차이가 같을 때, 낮은 점수를 더 많이 맞힌 경우가 더 좋은 경우인지 판단
    private boolean isBetter(int[] candidate, int[] current) {
        for (int i = 10; i >= 0; i--) {
            if (candidate[i] > current[i])
                return true;
            else if (candidate[i] < current[i])
                return false;
        }
        return false;
    }
}

---

🔍 코드 설명

📌 1. 초기 값 설정

answer = new int[11];
now = new int[11];

• answer[]: 최적의 화살 배분을 저장할 배열
• now[]: 현재 화살 배분 상태를 저장할 배열

---

📌 2. 어피치의 초기 점수 계산

for (int i = 0; i < 10; i++) {
    if (info[i] != 0)
        score += (10 - i);
}

• 어피치가 맞힌 점수 영역의 총 점수를 구함

---

📌 3. 백트래킹(DFS) 탐색

dfs(0, n, 0, score, info);

• 점수 영역(0~10)을 순차적으로 탐색
• count: 남은 화살 개수
• sum: 현재 라이언 점수
• s: 현재 어피치 점수

---

📌 4. 모든 점수를 탐색했을 때 (Base Case)

if (depth == 10) {
    now[10] = count;
    int diff = sum - s;

    if (diff > maximum) {
        maximum = diff;
        found = true;
        answer = now.clone();
    } 
    else if (diff == maximum) {
        if (isBetter(now, answer))
            answer = now.clone();
    }

    now[10] = 0;
    return;
}

• 10개의 점수 탐색이 끝나면 남은 화살을 0점에 배분
• 최대 점수 차이를 갱신
• 점수 차이가 같다면 더 낮은 점수를 많이 맞힌 경우를 선택

---

📌 5. 라이언이 어피치보다 1개 더 맞히는 경우

if (count >= info[depth] + 1) {
    now[depth] = info[depth] + 1;

    if (info[depth] > 0)
        dfs(depth + 1, count - (info[depth] + 1), sum + (10 - depth), s - (10 - depth), info);
    else
        dfs(depth + 1, count - (info[depth] + 1), sum + (10 - depth), s, info);

    now[depth] = 0;
}

• 어피치보다 1개 더 맞혀 점수를 가져가는 경우

---

📌 6. 점수를 포기하는 경우

dfs(depth + 1, count, sum, s, info);

• 현재 점수를 포기하고 다음 점수로 진행

---

🔥 시간 복잡도 분석

연산 최악의 경우 수행 횟수 시간 복잡도

dfs 호출

2^10 (1024번)

O(2^10) ≈ O(1024)

✅ 완전 탐색이지만 범위가 작아 충분히 가능

---

🏆 정리

✅ 핵심 포인트

✔ DFS(백트래킹)으로 모든 경우의 수 탐색
✔ 점수 차이가 가장 큰 경우를 선택
✔ 점수 차이가 같다면, 낮은 점수를 많이 맞힌 경우를 선택

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다!