코테 준비/DP
[프로그래머스] 등굣길
imsmile2000
2024. 2. 6. 11:11
처음에는 조합? 확률과 통계 공식으로 풀어보려했는데 생각해보니 그렇게 복잡하게 풀 필요가 없었다.
테두리를 1로 초기화하고 puddle이 있는 좌표는 0으로 하여
dp[i][j]=dp[i-1][j]+dp[i][j-1]
을 사용해 풀면 되는 것이었다!
def solution(m, n, puddles):
dp=[[1]*n for _ in range(m)]
for p in puddles:
dp[p[0]-1][p[1]-1]=0
for i in range(1,m):
for j in range(1,n):
if dp[i][j]!=0:
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
return dp[m-1][n-1]
처음에는 puddle 위치를 0으로 만들고 dp 적용하면 되겠다 싶었는데 두세개의 테스트케이스에서 실패가 떴다.
이유는 puddle이 테두리에 있는 경우를 고려하지 않았기 때문이었다.
테두리에 puddle이 있는 경우 그 이후의 테두리도 0으로 초기화 해주어야한다.
def solution(m, n, puddles):
dp=[[1]*n for _ in range(m)]
for p in puddles:
dp[p[0]-1][p[1]-1]=0
for i in range(m):
if dp[i][0]==0:
for t in range(i,m):
dp[t][0]=0
break
for j in range(n):
if dp[0][j]==0:
for t in range(j,n):
dp[0][t]=0
break
for i in range(1,m):
for j in range(1,n):
if dp[i][j]!=0:
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
return dp[m-1][n-1]
적용해주면 성공!
