#풀이
예시보기
ex1) 문제 처럼 7g 인 경우를 보자.
1g: 고리를 풀면 무조건 생긴다.
2g: 다른 고리들의 합으로 만들 수 없으므로 처음 (만들고 싶은)g은 2g이다.
현재 상황: 2g + 1g + 4g
3g: 2g + 1g 이다.
4g: (나머지)g 이다.
5g: 4g + 1g
6g: 4g + 2g
7g: 모든 고리들의 합
이렇게 차근차근 고리들을 만들어 가면 된다. 고리를 2회 이상으로 푸는 경우는 어떻게 될까?
ex2) 13g 인 경우도 한번 해보자.
1회)
1g: 고리를 한번 풀면 무조건 생긴다.
2g: 다른 고리들의 합으로 만들 수 없으므로 (만들고 싶은)g은 2g이다.
현재 상황: 2g + 1g + 7g
3g: 2g +1g 이다.
4g: 만들수가 없으므로 고리를 2회 푸는 경우를 생각하자.
2회)
1g: 고리를 풀면 무조건 생긴다.
2g: 1g + 1g 고리를 2회 풀었기 때문이다.
3g: 기존에 있는 고리들로 만들 수 없기 때문에 (만들고 싶은)g은 3g이다.
현재 상황: 3g + 1g +1g + ?? + ??
4g: 3g + 1g
5g: 3g + 1g + 1g
6g: 기존에 있는 고리들로 만들 수 없기 때문에 (2번째로 만들고 싶은)g은 6g이다.
현재 상황: 3g + 1g + 6g +1g +2g
7g: 6g + 1g
8g: 6g +1g + 1g
9g: 6g +3g
10g: 6g + 3g +1g
11g: 6g + 3g + 1g + 1g
12g: 6g + 3g + 2g + 1g
13g: 모든 고리들의 합
접기 고리를 푼 횟수로 최대 몇g 까지 만들수 있는지 알아내면, 최대 보다 작은g은 만들 수 있다.
- 1회: 2 + 1 + 4
- 2회: 3 + 1 + 6 + 1 + 12
- 3회: 4 + 1 + 8 + 1 + 16
- n회: n + 1 + 2n + 1 + 3n + 1 ...
-> (2^(n+1) -1) * (n+1) + n
| chain=int(input()) a=2 for n in range(1,61): a *= 2 max = (a - 1)*( n + 1 ) + n if chain <= max : print(n) break | cs |
댓글 쓰기