# [Silver I] 가주아 [문제 링크](https://www.acmicpc.net/problem/16464) ## 문제 설명 <p>평소 도박을 즐겨하는 병규는 방학을 맞아, 한국 최대의 카지노 코스모스랜드를 찾았다. 일확천금의 꿈에 부풀어 여러 게임에 참여했지만, 입장 한 시간 만에 재산의 절반을 탕진하고 말았다.</p> <p>평소 블랙잭에 자신이 있었던 병규는, 마지막 희망으로 블랙잭 테이블에 앉았다. 코스모스랜드에서는 일반 블랙잭과는 조금 다른 방식의 블랙잭인 "HY블랙잭" 이라는 게임을 만들어서 진행 중이었다. 규칙은 다음과 같다.</p> <ul> <li>딜러가 로또 기계에서 2 이상의 정수가 써진 공을 하나 뽑는다. 이때 나온 수가 K라면 딜러의 수는 K가 된다.</li> <li>플레이어는 딜러의 수 K를 확인하고, 카드를 받아 그 합이 정확히 K가 되도록 하면 게임에서 승리하게 된다.</li> <li>각 카드에는 정수가 쓰여 있다. 일반 트럼프카드와 달리 1 이상 K-1 이하의 정수가 한 번씩 쓰여 있고, 오름차순으로 정렬되어 있다. 플레이어는 연속된 몇 장의 카드만 골라서 받을 수 있다.</li> <li>만약 연속된 카드의 합으로 딜러의 수 K를 만들 수 없을 경우, 플레이어가 패배한다.</li> </ul> <p>예를 들어, 딜러가 뽑은 공의 수가 9라면, 병규는 연속된 카드 2,3,4의 합으로 9를 만들 수 있으므로 병규의 승리가 된다. 하지만 딜러가 뽑은 공의 수가 4라면, 연속된 카드의 합으로 4를 만들 수 없으므로 병규의 패배가 된다.</p> <p>K가 주어졌을 때, 병규가 이길 수 있는지 없는지 알려주는 프로그램을 작성하여 병규를 도와주자!</p> ## 입력 <p>첫 번째 줄에, 테스트케이스의 수 N (1 ≤ N ≤ 10³)이 주어진다. 그 다음 줄부터 N개의 줄에 테스트케이스가 한 줄에 하나씩 주어진다. 각 테스트케이스에는 딜러가 뽑은 공의 수 K (2 ≤ K ≤ 10⁹)가 주어진다.</p> ## 출력 <p>각 경우마다 병규가 이길 수 있다면, "Gazua"를, 병규가 이길 수 있는 방법이 없다면 "GoHanGang"을 출력한다. (큰따옴표는 출력하지 않는다)</p> ## 풀이 #### n이 홀수인 경우 n/2 + (n+1)/2 로 항상 만들 수 있다. #### n이 짝수인 경우 홀수로 나누어 떨어질 때, 그 홀수를 구성하는 요소의 좌우를 늘려가며 항상 구할 수 있다. ex) 15 = 7+8, 30 = 15 * 2 = 6+7+8+9 #### 따라서 못구하는 경우는 n이 2의 제곱수인 경우 뿐이다. ``` c++ #include<bits/stdc++.h> using namespace std; bool isSquareByTwo(int n) { while(n%2==0) n>>=1; return n!=1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; cout << (isSquareByTwo(n) ? "Gazua\n" : "GoHanGang\n"); } } ```