백준 / 24040 / B 예쁜 케이크 / Good Bye, BOJ 2021! / 파이썬, python, pypy

24040번: 예쁜 케이크

 

2021년 12월 31일 백준 대회엔 Good Bye, BOJ 2021!에 참가했다.

A부터 G까지의 문제가 난이도 순으로 정렬되어, 앞 부분은 쉬운 문제일 것이라 생각했는데

 

1번 문제는 간단하게 해결했지만, 2번 문제인 예쁜 케이크에서 많은 시간을 사용했다..

 

처음에는 1~N까지의 모든 경우를 체크하면서 "i+(N-i) % 3 == 0"을 체크했는데, 시간초과가 나왔다.

 

문제를 다시 살펴보니, T가 1000까지고, N이 10**18이였으니 당연한 TLE...

 

 

한참 생각해도 브루트포스 방식말고 떠오르지 않아서, 그냥 일단 가능한 모든 경우를 나열해보니

 

패턴을 찾을 수 있었다. 

(찾고보니 1분 컷 가능했을듯...)

 

 

문제의 접근법은 모든 숫자를 3의 배수로? 표현해서 수학적으로 접근했어야한다.

 

즉, 모든 가로, 세로의 길이는 3n, 3n+1, 3n+2로 표현이 가능하다.

 

그럴경우, 두 변의 길이의 합이 3의 배수가 될 수 있는 경우는 2가지 경우밖에 없다.

    1. 3n + 3n = 3n

    2. 3n+1 + 3n+2 = 3n + 3 = 3n

 

합이 3의 배수일 때, 곱을 구해보면

    1. 9n^2

    2. 9n^2 + 9n + 2

 

1번의 경우는 모두 9의 배수

2번의 경우는 3으로 나누었을 때 2가 남는 수

 

즉, 입력 N이 주어졌을 때

9의 배수이거나, 3으로 나누었을 때 2가 남는지를 확인하면 바로 확인이 가능하다.

 

그러므로 O(1)*T이므로 시간을 만족하면서 정답을 구할 수 있다.

 

import sys
 
for _ in range(int(sys.stdin.readline())):
    N = int(sys.stdin.readline())
 
    if N % 9 == 0 or N % 3 == 2:
        print('TAK')
    else:
        print('NIE')