알고리즘
2차원 배열 초기화와 DP
Rogue One
2024. 2. 2. 17:38
https://www.acmicpc.net/problem/9625
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
예전의 감이 돌아오는것일까? 알고리즘 문제들을 10분컷으로 풀기 시작했다. 사실 DP만 주구장창 팠던 경험이 있어서 DP만 그런거같긴한데 기분이야 좋다. 사실 DP는 점화식만 잘 세우고 범위만 잘잡으면 어렵지 않다. 진짜 어려운것은 이 문제가 어떤 알고리즘으로 풀어야 하는지 파악하는것이다.
아무튼 왜 글을 썼냐면, 2차원배열에서 내가 잘못알던 부분이 있어서였다.
dp = [[0] for _ in range(K+1)]
dp[0][0]=1
dp[1][0]=0
처음에 무의식중에 작성한 코드다.
dp = [[0,0] for _ in range(K+1)]
dp[0]=[1,0]
이렇게 작성되어야 한다. 그러니까, 2차원 배열 초기화할때 리스트의 리스트라는걸 잊지말자
dp = [[0] * cols for _ in range(rows)]로 적어야 한다는 말이다.
이렇게 한 글을 끝내기는 아쉬우니,
https://www.acmicpc.net/problem/2302
2302번: 극장 좌석
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)
www.acmicpc.net
나중에 복습할때 이문제도 다시 풀어보자