풀이
보기에는 쉬운 문제처럼 보였으나, 막상 풀어보면 구현하는데 어려움을 겪었던 문제다.
문제에서 gin이 나올 수 있는 경우는 다음과 같다.
- 트리플리트 + 트리플리트
- 트리플리트 + 런 or 런 + 트리플리트
- 런 + 런
이 중에서 특히, 런(3가지의 숫자가 서로 연속적으로 오는 경우)에서의 경우가 어려웠는데트리플리트 이후의 남은 숫자의 처리와 함께 런에서의 처리가 힘이 들었다.**
예를 들자면,
6개의 숫자가 1 1 1 1 2 3으로 주어진다고 하면,
1. 세 개의 1로 트리플리트를 만들고,
2. 남은 하나의 1과 남은 2, 3으로 런을 만들면
3. gin이 될 수 있다.
여러가지를 생각했으나, 떠오르는 방법은 런이나, 트리플리트가 성립되는 경우를 제외하는 것이다.
이때, 제외하는 수를 주의해야 하는데, 차칫하면 중복이 되지 않는 경우가 생길 수 있다는 것이다.
6개의 숫자가 2 2 3 3 4 4으로 주어진다고 하면,
1. 2, 3, 4가 런이 된다.
2. 런이 된 수를 제외하더라도 런이 또 될 수 있다.
이 경우 또한 생각해야 하는 것이다.
나는 이런 경우를 3의 몫과 평균으로 해결해보았다.
트리플리트는 무조건 3개가 동시에 같은 수가 나와야 성립한다. 즉, 해당 성립 횟수는 3으로 나누었을때의 몫과 같다는 것이 된다.
또한, 런의 횟수는 해당 수의 평균의 정수 값으로 알 수 있다.
예를 들어 6개의 숫자 빈도가 1, 2, 2, 0, 1이라고 가정하자(옆에 있는 것은 연속된 수이다.)
그렇다면 런의 횟수는 연속된 수의 평균인 (1 + 2 + 2) / 3 = 1이 되는 것이다.
그리고 해당 횟수를 제외한 남은 수는 0, 1, 1... 이 되는 것이다.
이때, 3으로 나누는 이유는 런이 성립되는 연속된 수가 3개이기 때문이다.
코드
코드를 보면 다음과 같다.
#include <iostream>
using namespace std;
int a[10]; /// 주어진 6개의 수의 빈도를 넣는 배열(0~9)
int n,i,tsw, rsw;
int main()
{
/// freopen("input.txt", "r", stdin); /// 읽기
for(i=0; i<6; i++){
cin >> n;
a[n] += 1;
}
/// 트리플리트
for(i=0; i<10; i++){
if(a[i] >= 3){ /// 트리플리트의 조건이 되는 수
int cnt = a[i] / 3; /// 횟수를 구한다.
tsw += cnt; /// 횟수만큼 트리플리트의 횟수가 된다.
a[i] -= cnt * 3; /// 사용된 수는 제거해준다.
}
}
/// 런
for(i=0; i<10; i++){
if(a[i] >= 1) { /// 런의 조건이 되는 수
if(a[i+1] != 0 && a[i+2] != 0) { /// 런의 조건이 되는 수 (연속)
int av = (a[i] + a[i+1] + a[i+2]) / 3; /// 평균의 정수값
rsw += av; /// 런의 횟수가 된다.
a[i] -= av, a[i+1] -= av, a[i+2] -= av; /// 평균만큼 횟수 차감
}
}
}
/// gin이 되는 경우
if(tsw == 2) cout << "gin";
else if(tsw == 1 && rsw == 1) cout << "gin";
else if(rsw == 2) cout << "gin";
else cout << "lose";
return 0;
}