[코딩테스트/프로그래머스]등굣길
💡생각
다이나믹프로그래밍이니깐 재귀나 반복을 이용해야하고 고등학생때 배웠던 확통 방식으로 풀어야한다는건 알겠는데 도저히 풀 수가 없어서 다른 사람의 코드를 보았음.
⏬다른사람의 코드
나는 문제를 봤을 때 좌표가 반대인 것을 고려할 생각을 하지 못했고 왜 1000000007로 나눈 나머지값을 리턴해야하는지 이해하지 못함.
또, 아래 코드를 보고 dp를 초기화하는 과정의 코드가 잘 이해가 안돼서 그 부분을 공부 해야겠다고 생각함.
🔗풀이 참고
https://dev-note-97.tistory.com/141
def solution(m, n, puddles):
puddles = [[q,p] for [p,q] in puddles] # 미리 puddles 좌표 거꾸로
dp = [[0] * (m + 1) for i in range(n + 1)] # dp 초기화
dp[1][1] = 1 # 집의 위치(시작위치)
for i in range(1, n + 1):
for j in range(1, m + 1):
if i == 1 and j == 1: continue
if [i, j] in puddles: # 웅덩이 위치의 경우 값을 0으로
dp[i][j] = 0
else: # 현재 칸은 왼쪽 칸, 위 칸의 합산!
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
return dp[n][m]
- 문제에서의 좌표가 일반적인 좌표와 반대이므로 puddles 좌표 거꾸로 함.
- dp: 결과 저장용 리스트.
집에서 학교까지 가는 길인 m x n 크기만큼 리스트를 만들어줌. - dp[1][1]에 집의 위치 지정.
- 이중 for문을 돌면서 웅덩이 위치의 경우에는 dp에 0을 저장, 그렇지 않을 경우에는 현재 칸의 왼쪽 칸과 위 칸에 저장된 값을 합산한 뒤 문제의 요구대로 1,000,000,007로 나눈 나머지 값을 저장함.
- 마지막으로 dp[n][m]에 저장된 값을 return함.
🔗프로그래머스 - 등굣길
https://programmers.co.kr/learn/courses/30/lessons/42898
Author And Source
이 문제에 관하여([코딩테스트/프로그래머스]등굣길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@click/코딩테스트프로그래머스등굣길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)