티스토리 뷰
문제 그림보고 솔직히 쫄았따
근데 사실 어려운 문제는 아니다 그냥 입력받는것만 주의하고
문제만 잘 읽으면 바로 풀 수 있다
여기서 서로 다른걸 내서 이겨야하므로 그냥 N! 만큼 보면된다
최대 9!이다!
나머지 두명은 순서를 주니까 말 그대로 구현하면 바로 답이 나온다
물론 나는 두명을 20까지 입력받아야하는데 n까지 입력받아서 30분간 슬픈짓했다
역시 고수가 되는건 어렵나..!
먼저 각각의 순서를 order에 차례대로 지우 경희 민호 0,1,2 로 넣어준다
지우는 1~N 까지 내기위해 배열에 넣어준다
그리고 game이라는 함수를 통해 게임을 시켜주면 된다
a,b 두명이 게임을 하면 처음 준 비교표를 통해 승자를 구할 수 있다
그리고 나머지 한명은 3-a-b다 왜냐면 셋의 합이 무조건 3이 나와야하므로
그냥 이렇게 하면 남은 한명을 쉽게 구할 수 있다
그렇게 셋을 게임시켜주고 누군가 한명이 k점을 만들면 return 시켜준다
그리고 그사람이 지우라면 1 을 출력하고 끝까지 지우가 못이기면 0이다!
여기서 헷갈렸던 부분은 2명이 20round까지 round별로 정해준 걸 내는 줄 알았는데
round가 아닌 순서다!
예를들어 2라운드에서 민호가 게임을 한다면 민호의 2번째 index가 아닌 1번째 index를 낸다
나는 round라고 생각해서 2라운드면 2번째로 하다가 답이 안나왔었따
어쨌든 크게 어려운 알고리즘보다 이해력과 구현을 필요로 하는 문제다!
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
int arr[11][11];
int order[3][22];
int score[3],cnt[3];
int game(int a,int b){
if(cnt[0]>n) return -1;
int win = arr[order[a][cnt[a]++]][order[b][cnt[b]++]];
if(win==2) win=a;
else if(win==0) win=b;
else win = max(a,b);
score[win]+=1;
if(score[win]==k) return win;
return game(3-a-b,win);
}
int main(){
scanf(" %d %d",&n,&k);
for(int i=1;i<=n;i++) order[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf(" %d",&arr[i][j]);
}
}
for(int i=1;i<=20;i++) scanf(" %d",&order[1][i]);
for(int i=1;i<=20;i++) scanf(" %d",&order[2][i]);
do{
score[0]=score[1]=score[2]=0;
cnt[0]=cnt[1]=cnt[2]=1;
if(game(0,1)==0) {
puts("1"); return 0;
}
} while(next_permutation(order[0]+1,order[0]+n+1));
puts("0");
}
|
'알고리즘 > BOJ' 카테고리의 다른 글
[백준] 17087 숨바꼭질 6 (0) | 2020.02.02 |
---|---|
[백준] 16987 계란으로 바위치기 (0) | 2020.02.02 |
[백준] 1103 게임 (0) | 2020.02.01 |
[백준] 17069 파이프 옮기기 2 (0) | 2020.02.01 |
[백준] 17135 캐슬 디펜스 (0) | 2020.02.01 |
댓글