문제 설명
- A와 B가 각각 N/2개의 주사위를 가지고 승부를 한다.
- 각 주사위는 6개의 면을 가진다.
- 주사위를 모두 굴린 후, 나온 수를 모두 합한 점수를 비교한다.
- 각 게임마다 주사위의 합이 더 큰 쪽이 승리한다.
- 가장 높은 승리 수를 가질 수 있는 주사위를 선택한다.
문제 해결 전략
시간 복잡도
최대 주사위의 개수는 10개이다.
10개 중에 5개를 가져가서 게임할 수 있는 조합의 수는
10C5 = 252개가 될 것이다.
그리고 각 주사위는 6개의 면을 가진다. 해당 문제를 brute-force하게 풀려고 한다면,
A가 5개의 주사위를 가져갔을 때, 5개의 주사위의 합을 한 번 구할 때마다 B가 5개의 주사위를 가져가서 모든 주사위의 합을 6^5의 경우를 비교하기 때문에 전체를 비교하려면 6^10이 될 것이다.
그렇게 되면, 252 X 6^10이 되는데, 이는 당연히 시간 초과이다.
이를 토대로 생각해 보면, A가 가져가서 모든 주사위의 경우를 구하는 수인 6^5가 된다.
그리고 B가 가져가서 모든 주사위의 경우를 구하는 수 또한 6^5가 된다.
각 주사위를 구하는 경우를 독립적으로 시행해서 구한 합들을 비교하는 것이 시간 초과를 해결할 수 있는 방법이다.
필자는 독립적으로 시행한 값을 비교하는 방법으로 이분 탐색을 사용했다.
그렇게 된다면, 10C5 X 6^5의 과정에서 각 값들을 비교하는 시간은 log2n시간이 걸리기 때문에 시간 초과에 걸리지 않게 된다.
주사위를 가져가는 조합
N개 중에 N/2를 뽑는 방법은 쉽다.
void go(vector<vector<int>> dice, int idx, int depth){
if(depth == N/2){
if(ret < processGame(dice)){
ret = processGame(dice);
int idx = 0;
for(int i = 0; i < N; i++){
if(visited[i]){
result[idx++] = i + 1;
}
}
}
return;
}
for(int i = idx; i < N; i++){
if(!visited[i]){
visited[i] = 1;
go(dice, i + 1, depth + 1);
visited[i] = 0;
}
}
}그냥 dfs를 통해 조합을 구해서 N/2를 가져가는 순간 게임을 진행한다.
A와 B 주사위를 가지고 구할 수 있는 합 구하기
int processGame(vector<vector<int>> dice){
vector<int> winCombi;
vector<int> loseCombi;
for(int i = 0; i < N; i++){
if(visited[i])
winCombi.push_back(i);
else
loseCombi.push_back(i);
}
goWin(dice, winCombi, 0, 0);
goLose(dice, loseCombi, 0, 0);
sort(win.begin(), win.end());
sort(lose.begin(), lose.end());
int sum = go_binary_search();
win.clear();
lose.clear();
return sum;
}위에서 구한대로 A가 가져가는 주사위 번호를 winCombi에 넣어주고, B가 가져가는 주사위 번호를 loseCombi에 넣어준다.
그것을 토대로 각 주사위로 구할 수 있는 모든 합을 구한다.
void goWin(vector<vector<int>> dice, vector<int> winCombi, int depth, int sum){
if(depth == N/2){
win.push_back(sum);
return;
}
for(int i = 0; i < 6; i++){
goWin(dice, winCombi, depth+1, sum + dice[winCombi[depth]][i]);
}
}void goLose(vector<vector<int>> dice, vector<int> loseCombi, int depth, int sum){
if(depth == N/2){
lose.push_back(sum);
return;
}
for(int i = 0; i < 6; i++){
goLose(dice, loseCombi, depth+1, sum + dice[loseCombi[depth]][i]);
}
}dfs를 통해서 모든 합을 구해서 win과 lose 벡터에 넣어준다.
winCombi나 loseCombi나 N/2개 만큼의 크기를 가지고 있으니까, depth가 N/2가 됐을 때의 합을 각 벡터에 넣어준다.
이분 탐색
int go_binary_search(){
int sum = 0;
for(auto& target : win){
int low = 0;
int high = lose.size();
int mid = 0;
while(low < high){
mid = (low + high) / 2;
if(target > lose[mid])
low = mid + 1;
else
high = mid;
}
sum += low;
}
return sum;
}사실 lower_bound()를 통해서 구하면 더 편하겠지만, 나는 그냥 구현하는 방법이 더 손에 익어서 직접 구현했다.
win 벡터에 있는 값을 하나씩 꺼내서 lose 벡터와 이분 탐색을 통해 해당 값이 어느 위치에 들어갈 수 있는 지를 탐색한다. 그 위치가 A보다 작은 값들이다.
즉, win 벡터에서 꺼낸 값보다 작은 값들은 A가 이긴 경우이기 때문에 해당 값을 더하여 반환한다.
해당 과정을 통해, 최대 값이 나오는 경우에 갱신해주며 주사위의 번호를 담아주면 된다.
코드
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int N, ret = -1;
int result[5];
int visited[11];
vector<int> win;
vector<int> lose;
void goWin(vector<vector<int>> dice, vector<int> winCombi, int depth, int sum){
if(depth == N/2){
win.push_back(sum);
return;
}
for(int i = 0; i < 6; i++){
goWin(dice, winCombi, depth+1, sum + dice[winCombi[depth]][i]);
}
}
void goLose(vector<vector<int>> dice, vector<int> loseCombi, int depth, int sum){
if(depth == N/2){
lose.push_back(sum);
return;
}
for(int i = 0; i < 6; i++){
goLose(dice, loseCombi, depth+1, sum + dice[loseCombi[depth]][i]);
}
}
int go_binary_search(){
int sum = 0;
for(auto& target : win){
int low = 0;
int high = lose.size();
int mid = 0;
while(low < high){
mid = (low + high) / 2;
if(target > lose[mid])
low = mid + 1;
else
high = mid;
}
sum += low;
}
return sum;
}
int processGame(vector<vector<int>> dice){
vector<int> winCombi;
vector<int> loseCombi;
for(int i = 0; i < N; i++){
if(visited[i])
winCombi.push_back(i);
else
loseCombi.push_back(i);
}
goWin(dice, winCombi, 0, 0);
goLose(dice, loseCombi, 0, 0);
sort(win.begin(), win.end());
sort(lose.begin(), lose.end());
int sum = go_binary_search();
win.clear();
lose.clear();
return sum;
}
void go(vector<vector<int>> dice, int idx, int depth){
if(depth == N/2){
if(ret < processGame(dice)){
ret = processGame(dice);
int idx = 0;
for(int i = 0; i < N; i++){
if(visited[i]){
result[idx++] = i + 1;
}
}
}
return;
}
for(int i = idx; i < N; i++){
if(!visited[i]){
visited[i] = 1;
go(dice, i + 1, depth + 1);
visited[i] = 0;
}
}
}
vector<int> solution(vector<vector<int>> dice) {
vector<int> answer;
N = dice.size();
go(dice, 0, 0);
for(int i = 0; i < N/2; i++){
answer.push_back(result[i]);
}
return answer;
}소감
최근 풀었던 문제중에 가장 어려웠다.
A와 B가 가져가는 주사위에서 모든 경우의 수를 구하는goWin와goLose를 구현하는 데에 조금 어려움을 많이 겪었는데, 맨 처음에 반복문으로 구하려다가 방식을 바꿨다.
사실 구현하는 데에 한참 걸렸음.
이분 탐색은 시간 초과를 잡기 위해 입출력 예제 #2를 보다가 겨우 떠올려서 풀었다.
여담으로 프로그래머스에서 긴 코드를 작성하기 너무 불편하다. 창이 너무 작아서 보이는 라인은 몇 줄 안되기 때문에 함수 모듈화하는 과정에서 더 복잡해지는 기분이 든다.
어쨌든 킵고잉 ~!
Reference
https://school.programmers.co.kr/learn/courses/30/lessons/258709
Code
https://github.com/im2sh/Algorithm/blob/main/Programmers/%5B2024%20KAKAO%20WINTER%20INTERNSHIP%5D/%5BLv3%5D%20%EC%A3%BC%EC%82%AC%EC%9C%84%20%EA%B3%A0%EB%A5%B4%EA%B8%B0.cpp
