백준 2193 문제 풀이 python

🐒 이친수

https://www.acmicpc.net/problem/2193

✍ 나의 풀이

n = int(input())

dp = [[0,0] for i in range(n+1)]

dp[1][1] = 1

for i in range(2,n+1):
    for j in range(2):
        if j == 0:
            dp[i][0] += dp[i-1][j]
            dp[i][1] += dp[i-1][j]
        else:
            dp[i][0] += dp[i-1][j]

print(sum(dp[n]))

DP 유형 문제풀이를 시작하고 그 난이도 때문에
문제에 후두려맞느라 자신감이 떨어져있었던 도중

DP 문제 중 처음으로 내 힘으로 푼 문제를 풀었다! 😊
못 풀줄 알고 시간도 안쟀는데 아마 3~40분 가량 걸렸을 것 같다.

🧠 문제 이해

나름의 고민했던 흔적이다.

내가 주목했던 부분은 1은 연속 될 수 없다와 0과 1의 갯수이다.

1은 연속될 수 없다, 0과 1의 갯수

가령 세자리수의 이친수는 100, 101이 있다.
다시말하면 세자리수의 이친수들 끝자리의 0의 갯수는 1개이고 1의 갯수는 1개이다.

0은 끝에 0 또는 1을 붙일수있다.
끝자리 0의 갯수를 1개 늘리고, 끝자리 1의 갯수를 1개 늘린다.

1은 끝에 0을 붙일 수 있다.
끝자리 0의 갯수를 1개 늘린다.

그렇다면 네자리수 이친수의 끝자리는 0이 2개, 1이 1개가 된다.
합치면 네자리수 이친수의 갯수가 3개인 것 이다.

확인해보면 네자리수 이친수는 1000, 1001, 1010 이다.

n자릿수 이친수들의 끝자리에 0과 1의 갯수를 이용해서 문제를 풀자!

구현

나는 이를 구현하기 위해 2차원 배열에 0과 1의 갯수를 저장하기로 했다.

dp = [[0,0] for i in range(n+1)] 
		# [[0,0],[0,0],[0,0] ...] 
	# 0~n자릿수까지 표현 할 수 있는 배열 생성
     # 각 자릿수들의 0의 갯수와 1의 갯수를 나타낼 수 있는 공간을 2차원 배열로 만듬
     
dp[1][1] = 1
	# 한자리수 이친수는 1 만 존재하며, 한자리수 에서 0의 갯수는 0, 1의 갯수는 1이다.

반복문을 통해서 만들어진 배열에 값들을 채워넣자.

for i in range(2,n+1):	# 두자릿수 부터 n자릿수까지
    for j in range(2):	 # 2차원 배열 검사
        if j == 0:	# 0의 갯수 검사
            dp[i][0] += dp[i-1][j]  # 이전항의 0의 갯수가 현재항의 0의 갯수가 됌
            dp[i][1] += dp[i-1][j]  # 이전항의 0의 갯수가 현재항의 1의 갯수가 됌
        else:	# 1의 갯수 검사
            dp[i][0] += dp[i-1][j] # 이전항의 1의 갯수를 현재항의 0의 갯수에 더해줌
            
            
print(sum(dp[n]))
	# n자릿수의 이친수들의 끝자리에 있는 0과 1의 갯수를 합쳐서 출력

후기

문제풀이가 재밌긴한데.. 어렵다..🥲

수정

for i in range(2,n+1):
    for j in range(2):
        if j == 0:
            dp[i][0] = dp[i-1][j] # += 가 필요없다
            dp[i][1] = dp[i-1][j]
        else:
            dp[i][0] += dp[i-1][j]

+=를 쓰나 =를 쓰나 결과는 같지만
개인적으로 =를 사용하는게 보기에 명확해보인다.