문제 설명
랜덤다이스로 재미있는 문제가 없나 싶었을 때 딱 나왔던 문제.
input으로 들어간 자연수 이하의 집합에서 한가지 조건을 만족하는 집합의 최대 크기를 구하는 문제이다.
조건은 다음과 같다.
if x in S, then 2x+2 not in S.
간단히 주어진 조건을 만족하는 집합S가 있고, 그 안의 모든 원소x에 대해서2x+2가S에 없으면 된다는 것이다.
문제에 있는 예시를 통해 설명해보자.
input에 4가 들어갔다면 주어진 집합은 {1,2,3,4}이다.
이 때 조건을 만족하는 집합 S를 생각해보면, 만약 S에 1이 들어갔다고 가정하자. 그렇다면 2*1+2 = 4는 S에 들어갈 수 없다.
따라서 조건을 만족하는 집합은 {1}, {2}, {3}, {4}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {1,2,3}, {2,3,4}가 있고, 이 때 집합의 최대 크기는 3이 되므로 output은 3이 출력되어야 한다.
풀이 원리 설명
처음 문제를 보고 조건을 만족하는 최대 집합은 어떻게 생겼을까를 먼저 떠올려봤다. 맨 처음에는 각 숫자 x에 대해 2x+2가 들어가지 못하니까 홀수집합을 먼저 떠올렸지만 이에 따라 들어갈 수 없는 짝수들과 들어갈 수 있는 짝수들을 생각하다보니 이 방법은 아니다 싶었기 때문에 reject..(글을 쓰면서 생각해본 것이지만, 몇가지 예시를 따져봤는데 모든 수에서 모든 홀수가 들어가는 최대 크기의 집합이 있기는 한 것 같다.. 24까지 따져봄.)
다음으로 떠올린 방법은 '큰 수부터 우겨넣어보자' 였다. 가장 큰 짝수2k가 집합에 들어갔다고 가정했을 때, 집합에 k부터 2k까지(홀수일 경우 2k+1까지) 들어갈 수 있다. 그리고 이 숫자들이 집합에 다 들어간다고 가정했을 때, 그 다음으로 들어갈 수 있는 큰 수들은 (k-3)//2이하의 숫자들로 이 수들은 2x+2를 계산했을 때 k 미만의 숫자가 나오게 되는 모든 수가 된다.
'''
1 --> 1.. 1
2 --> 12.. 2
3 --> 123.. 3
4 --> 234.. 3
5 --> 2345.. 4
6 --> 3456.. 4
7 --> 34567.. 5
8 --> 45678.. 5
9 --> 456789.. 6
10 --> 1 5~10.. 7 == P(1)+(10+1)//2+1
11 --> 1 5~11.. 8 == P(1)+(11+1)//2+1
12 --> 1 6~12.. 8 == P(1)+(12+1)//2+1
13 --> 1 6~13.. 9 == P(1)+(13+1)//2+1
14 --> 12 7~14.. 10 == P(2)
15 --> 12 7~15.. 11
16 --> 12 8~16.. 11
17 --> 12 8~17.. 12
18 --> 123 9~18.. 13 P(3)
19 --> 123 9~19.. 14
20 --> 123 10~20.. 14
21 --> 123 10~21.. 15
22 --> 234 11~22.. 15
24 --> 234 12~24.. 16
'''위의 주석은 이 방식으로 집합을 구했을 때 이 집합의 크기가 최대가 될지 확인하기 위한 것이다. 결과적으로 이 방법이 최대 크기를 구하는 옳은 방법이라는 것이라는 확신이 들었었고, 그거를 코드로 구현하게 되었다.
답안 코드
답안 코드는 결과적으로 간단하다. 위의 예시로 써놓은 10 이상의 숫자를 보면 알겠지만 가장 큰 숫자를 포함한 연속된 숫자들의 집합의 크기를 계산한 후 재귀 형식으로 숫자를 넘겨주며 계산하는 것을 더하는 꼴로 계산이 이루어진다.
(최대 input size가 101개로 이루어진 숫자이기 때문에 sys.stdin.readline()은 굳이 쓰지 않았다.)
def calc(n):
if n<4:
return n
elif n<10:
return ((n+1)//2+1)
else:
return calc((n//2-3)//2)+(n+1)//2+1
print(calc(int(input())))한큐에 통과한건 자랑!
