[프로그래머스][C++] 양궁대회
양궁대회
문제 링크
분석
11개의 점수 구간으로 10점부터 0점까지 있습니다.
특정 점수 구간에 화살을 가장 많이 맞춘 사람이 점수를 가져갑니다.
만약, 특정 점수에 같은 개수의 화살을 맞췄을 경우 어피치가 점수를 가져갑니다.
info는 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열입니다.
n은 라이언이 쏠 수 있는 화살의 개수입니다.
라이언이 가장 큰 점수로 이길 수 있는 방법을 구해야 합니다.
만약, 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 반환해야 합니다.
DFS와 백트래킹을 사용해 조합을 탐색해볼 수 있습니다.
풀이
#include <vector>
using namespace std;
// 최대 점수 차이를 저장하는 변수
int maxDiff = 0;
// 화살 분배가 가장 잘 된 경우를 저장하는 배열
vector<int> answer;
// DFS로 가장 큰 점수로 이길 수 있는 방법을 구하는 함수
// info: 어피치의 화살 분배 정보
// currentInfo: 현재 라이언의 화살 분배 정보
// n: 남은 화살 수
// index: 현재 점수 인덱스
void dfs(const vector<int>& info, vector<int>& currentInfo, int n, int index)
{
// 모든 점수 구간을 탐색한 경우
if (index == info.size())
{
// 남은 화살이 있다면
if (n > 0)
{
// 남은 화살은 0점에 몰아준다.
currentInfo[10] += n;
}
// 라이언과 어피치의 점수를 저장할 변수
int lionScore = 0;
int apeachScore = 0;
// 라이언과 어피치의 점수 총합을 구한다.
for (int i = 0; i < info.size(); ++i)
{
// 현재 점수를 둘 다 맞추지 못한 경우
if (info[i] == 0 && currentInfo[i] == 0)
{
continue;
}
// 라이언이 더 많이 맞혔다면 라이언이 점수 획득
if (currentInfo[i] > info[i])
{
lionScore += 10 - i;
}
// 어피치와 같거나 적게 맞췄다면 어피치가 점수 획득
else
{
apeachScore += 10 - i;
}
}
// 라이언의 점수 총합이 더 큰 경우
if (lionScore > apeachScore)
{
// 라이언과 어피치의 점수 차이를 구한다.
int diff = lionScore - apeachScore;
// 현재 구한 점수가 기록된 최대 차이보다 크다면
if (diff > maxDiff)
{
// 최대 기록을 갱신하고, 배열 정보를 저장한다.
maxDiff = diff;
answer = currentInfo;
}
// 만약 현재 구한 점수가 기록된 최대 점수 차이와 같다면
else if (diff == maxDiff)
{
// 반복문으로 가장 낮은 점수 구간부터 비교한다.
for (int i = info.size(); i >= 0; --i)
{
// 가장 낮은 점수를 더 많이 맞춘 경우이므로 우선순위가 높다.
if (currentInfo[i] > answer[i])
{
answer = currentInfo;
break;
}
// 가장 낮은 점수를 더 적게 맞췄으므로, 높은 점수는 확인할 필요가 없다.
else if (currentInfo[i] < answer[i])
{
break;
}
}
}
}
// 백트래킹이며, 마지막에 추가했던 화살을 다시 되돌립니다.
if (n > 0)
{
currentInfo[10] -= n;
}
return;
}
// 현재 점수를 라이언이 얻기 위해서 필요한 화살의 수를 구합니다.
int requiredArrow = info[index] + 1;
// 남은 화살의 수가 충분한 경우
if (n >= requiredArrow)
{
// 사용한 화살 기록
currentInfo[index] = requiredArrow;
// 다음 점수 탐색
dfs(info, currentInfo, n - requiredArrow, index + 1);
// 백트래킹이며, 이번에 사용한 화살 기록을 되돌립니다.
currentInfo[index] = 0;
}
// 해당 점수를 포기하고 다음 점수를 탐색하는 경우
dfs(info, currentInfo, n, index + 1);
}
vector<int> solution(int n, vector<int> info) {
// 라이언이 맞힌 과녁 점수의 개수를 담은 정수 배열
vector<int> currentInfo(info.size(), 0);
dfs(info, currentInfo, n, 0);
// 점수 차이가 0 이상인 경우가 한 번도 없다면 -1을 반환해야한다.
if (maxDiff == 0)
{
return {-1};
}
return answer;
}
성능 요약
시간 복잡도는 $O(22528)$입니다.
- DFS의 탐색 깊이 11, 최대 2개의 분기 $O(2^{11} = O(2048))
- 각 분기에서 점수 계산 반복문 $O(11)$
- $O(2048 \times 11) = O(22528)$
공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.
- 화살 분배가 가장 잘 된 경우를 저장하는 배열
vector<int> answer$O(11)$ - 라이언이 맞힌 과녁 점수의 개수를 담은 정수 배열
vector<int> currentInfo$O(11)$ - DFS의 탐색 깊이 $O(11)$
- $O(11) + O(11) + O(11)$
테스트 성능
테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.03ms, 4.15MB)
테스트 3 〉 통과 (0.03ms, 4.22MB)
테스트 4 〉 통과 (0.02ms, 4.14MB)
테스트 5 〉 통과 (0.03ms, 4.14MB)
테스트 6 〉 통과 (0.03ms, 4.2MB)
테스트 7 〉 통과 (0.02ms, 4.15MB)
테스트 8 〉 통과 (0.02ms, 4.21MB)
테스트 9 〉 통과 (0.02ms, 4.15MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.02ms, 4.21MB)
테스트 12 〉 통과 (0.02ms, 3.63MB)
테스트 13 〉 통과 (0.03ms, 4.14MB)
테스트 14 〉 통과 (0.04ms, 3.67MB)
테스트 15 〉 통과 (0.03ms, 4.2MB)
테스트 16 〉 통과 (0.03ms, 4.21MB)
테스트 17 〉 통과 (0.02ms, 3.64MB)
테스트 18 〉 통과 (0.02ms, 4.19MB)
테스트 19 〉 통과 (0.01ms, 4.13MB)
테스트 20 〉 통과 (0.03ms, 4.14MB)
테스트 21 〉 통과 (0.05ms, 4.43MB)
테스트 22 〉 통과 (0.03ms, 3.6MB)
테스트 23 〉 통과 (0.02ms, 4.15MB)
테스트 24 〉 통과 (0.04ms, 4.16MB)
테스트 25 〉 통과 (0.04ms, 3.62MB)
댓글남기기