[Python] 백준 16888 루트 게임

문제 링크 : https://www.acmicpc.net/problem/16888

16888번: 루트 게임

1. 접근 방법

소수 판정 에라토스테네스 체와 비슷한 방식으로 해결될 것이라 생각이 들었다.

처음에는 각 조건마다 다음 턴을 거꾸로 탐색하는 과정을 반복했는데, 시간이 생각보다 많이 걸려서, 에라토스테네스 체에서도 사용하는 아이디어인, 소수를 발견하면 배수를 모두 소수가 아님을 표시하는 방법을 채용하여 해결했다.

 

 

2. 풀이 코드

🖥python코드

import sys
input = sys.stdin.readline


dp = [False] * (10 ** 6 + 1)

# 제곱수 먼저 확인
for i in range(1, 10 ** 3 + 1):
    dp[i * i] = True

# 나머지 확인
for i in range(2, 10 ** 6 + 1):
    if not dp[i]:
        # 제곱수를 더하면서 True로 바꿔주기
        for s in range(1, 10 ** 3 + 1):
            if i + s * s >= 10 ** 6:
                break
            dp[i + s * s] = True

for _ in range(int(input())):
    if dp[int(input())]:
        print('koosaga')
    else:
        print('cubelover')

📕코드 해설

각 시작숫자에 일 때 이길 수 있는지 확인하는 dp리스트를 만들었다. True일 때, 해당 숫자로 시작하면 이길 수 있다.

우선, 10 ^ 3까지 확인하면서 각각의 제곱수는 한번에 0으로 만들 수 있으므로 True로 바꿔주었다.

다음, 2부터 10 ^ 6까지 확인하면서 False일 때, 제곱수를 더한 숫자를 모두 True로 바꿨다.

 

https://stackoverflow.com/questions/51625314/why-vv-is-faster-than-v2-in-python/51625533

Why v*v is faster than v**2 in python

**을 사용하면 함수호출이 발생해서 두 수를 곱해서 처리하는 것보다 느리다.

이 문제에서도 ** 대신 두 수를 곱하는 방식으로 해결하면 조금 더 시간 단축이 가능하다.

 

 

3. 생각 정리

**이 함수호출로 해결되는 것은 기본일 수도 있지만, 떠올리지 못한 게 아쉬움이 남으면서, 많이 부족하다고 느낀 계기도 되었다.

이런 단순하지만, 시간적 제한이 강한 문제일수록 단순함을 잘 추구해야하는 한다고 생각하게 되는 문제였다.