한양대학교 프로그래밍 경시대회

최근에는 백준에 있는 한양대학교 프로그래밍 경시대회 문제를 몇가지 풀어보고 있는데 재미있는 문제가 있어 공유해보고자 한다.

가주아(16464번)

문제

평소 ㄷㅗㅂㅏㄱ을 즐겨하는 병규는 방학을 맞아, 한국 최대의 ㅋㅏㅈㅣㄴㅗ 코스모스랜드를 찾았다. 일확천금의 꿈에 부풀어 여러 게임에 참여했지만, 입장 한 시간 만에 재산의 절반을 탕진하고 말았다.

평소 블랙잭에 자신이 있었던 병규는, 마지막 희망으로 블랙잭 테이블에 앉았다. 코스모스랜드에서는 일반 블랙잭과는 조금 다른 방식의 블랙잭인 "HY블랙잭" 이라는 게임을 만들어서 진행 중이었다. 규칙은 다음과 같다.

딜러가 로또 기계에서 2 이상의 정수가 써진 공을 하나 뽑는다. 이때 나온 수가 K라면 딜러의 수는 K가 된다.
플레이어는 딜러의 수 K를 확인하고, 카드를 받아 그 합이 정확히 K가 되도록 하면 게임에서 승리하게 된다.
각 카드에는 정수가 쓰여 있다. 일반 트럼프카드와 달리 1 이상 K-1 이하의 정수가 한 번씩 쓰여 있고, 오름차순으로 정렬되어 있다. 플레이어는 연속된 몇 장의 카드만 골라서 받을 수 있다.
만약 연속된 카드의 합으로 딜러의 수 K를 만들 수 없을 경우, 플레이어가 패배한다.
예를 들어, 딜러가 뽑은 공의 수가 9라면, 병규는 연속된 카드 2,3,4의 합으로 9를 만들 수 있으므로 병규의 승리가 된다. 하지만 딜러가 뽑은 공의 수가 4라면, 연속된 카드의 합으로 4를 만들 수 없으므로 병규의 패배가 된다.

K가 주어졌을 때, 병규가 이길 수 있는지 없는지 알려주는 프로그램을 작성하여 병규를 도와주자!

코드 1

def sum_of_straight(N):
  return (N*(N+1))//2

N=int(input())
for _ in range(N):
  K=int(input())
  check=False
  for i in range(1,K):
    for j in range(1,i):
      if K==sum_of_straight(i)-sum_of_straight(j):
        check=True
        break
    if check==True:
      break
  if check==True:
    print("Gazua")
  else:
    print("GoHanGang")

풀이 1

가장 먼저 작성한 코드는 자연수의 합 공식을 이용해서 브루투포스 방식으로 이중 반복문을 돌려보았다. 모든 경우의 수를 탐색해서 가능한지 탐색하는 방법을 시도하자 당연하게도 시간초과가 나왔다.

코드 2

import sys
input=sys.stdin.readline

def sum_of_straight(N):
  return (N*(N+1))//2

N=int(input())
for _ in range(N):
  K=int(input())
  a=1
  check=False
  for x in range(1,K):
    if sum_of_straight(x)>=K:
      a=x
      break
  for i in range(a,K):
    for j in range(0,i):
      temp=sum_of_straight(i)-sum_of_straight(j)
      if K==temp:
        check=True
        break
      if temp<K:
        break
      
    if check==True:
      break
  if check==True:
    print("Gazua")
  else:
    print("GoHanGang")

풀이 2

두번째로 작성한 코드 역시 브루투포스 방식에서 필요없는 부분의 반복을 예외처리해서 줄여보았는데 다시 시간초과가 나왔다. 이를 확인하고 브루투포스 방식이 아닌 수학적인 방법으로 풀이가 가능한지 알아보았다.

코드 3

import sys
input=sys.stdin.readline

def sum_of_straight(N):
  return (N*(N+1))//2

N=int(input())
for _ in range(N):
  K=int(input())
  check=False
  for i in range(2,K):
    if (K-sum_of_straight(i))%i==0:
      check=True
      break
    if K<sum_of_straight(i):
      break
  if check==False:
    print("GoHanGang")
  else:
    print("Gazua")

풀이 3

연속된 자연수의 합을 구하는 새로운 방식을 찾아보고 다시 코드를 작성하였는데 정말 생각지도 못한 아이디어였다.
우선 알아보고자 하는 수를 K라고 할 때, K를 두 개의 연속된 수의 합으로 표현할 수 있는지 확인하는 방법은 다음과 같다. K-(1+2)%2==0 만약 K를 19라고 할 때, 여기에 3을 빼고 2로 나누면 몫이 8, 나머지가 0이 된다. 그렇다면 19는 1과 2에 각각 8을 더한 9와 10의 합이 된다. 이와 마찬가지로 n개로 표현하는 방법을 반복해 가능한 경우가 있는지 확인한다.

생각지도 못한 간단한 아이디어로 문제를 해결하다니 수학은 정말 신기했다!

또한 벨로그에 부적절한 단어가 들어가면 자동으로 비공개 처리가 된다고 한다. 이 포스팅 문제에 있는 'ㄷㅗㅂㅏㄱ'과 같은 단어로 인해 비공개처리를 당했다.