지나가던 개발자
[Python] 백준 2226번(이진수) 문제 풀이 본문
n = int(input())
if n <= 2:
print(n-1)
else:
binaryZeros = 1
for i in range(3, n):
if i % 2 != 0:
binaryZeros = binaryZeros*2 + 1
continue
binaryZeros = binaryZeros*2 - 1
print(binaryZeros)
골드4 문제 치고는 굉장히 쉬운 것 같다.
dp 문제인데, n에 따른 이진수의 변화와 정답의 변화는 다음과 같다.
| n | 1 | 2 | 3 | 4 | 5 |
| 이진수 | 1 | 01 | 1001 | 01101001 | 1001011001101001 |
| 정답 | 0 | 1 | 1 | 3 | 5 |
정답은 3부터 오른쪽으로 갈수록 n이 홀수일 때는 (정답)*2+1, n이 짝수일 때는 (정답)*2-1의 값을 가지는 것을 볼 수 있다.
이 글을 쓰는 데 도움이 되었던 자료:
https://velog.io/@xx0hn/BOJ-Python-2226%EB%B2%88-%EC%9D%B4%EC%A7%84%EC%88%98
[ BOJ / Python ] 2226번 이진수
이번 문제는 DP를 통해 해결하였다. 수열은 1 -> 01 -> 1001 -> 01101001 -> 1001011001101001 -> ... 으로 구성된다. 이때 만들어진 문자열들을 반으로 잘라 보면 다음과 같은 규칙을 찾을 수 있다.앞쪽과 뒷쪽
velog.io
'PS > Python' 카테고리의 다른 글
| [Python] 백준 11944번(NN) 문제 풀이 (0) | 2022.09.22 |
|---|---|
| [Python] 백준 6219번(소수의 자격) 문제 풀이 (0) | 2022.09.18 |
| [Python] 백준 11170번(0의 개수) 문제 풀이 (0) | 2022.09.18 |
| [Python] 백준 11966번(2의 제곱인가?) 문제 풀이 (0) | 2022.09.16 |
| [Python] 백준 2108번(통계학) 문제 풀이 (0) | 2022.09.15 |
'PS/Python' Related Articles
more
Comments