동적계획법 (Dynamic Programming) | DP
🌏 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 첫 번째 풀이
def solution(m, n, puddles):
dp = [[-1 for _ in range(m)] for _ in range(n)]
dp[0][0] = 0
for i in range(1,m):
dp[0][i] = 1
for i in range(1,n):
dp[i][0] = 1
for puddle in puddles:
dp[puddle[1]-1][puddle[0]-1] = 0
for i in range(n):
for j in range(m):
if dp[i][j] == -1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1] % 1000000007

고딩 때 경우의 수 문제 풀듯이 그림까지 그려가며 코드 짰는데 개같이 실패하였다.
👁 문제점 분석
가로-세로 1열을 1로 채워주었는데 이전에 물웅덩이가 나오면 앞으로 나아갈 수 없으므로
물웅덩이 이후는 0으로 처리해주어야 한다!
👁 반례
질문하기에 천사님이 남겨주신 반례덕분에 문제점을 발견할 수 있었다.
질문하기에 따봉박기가 없는게 너무 아쉽다 하 감사함다 사랑함다❤️
print(solution(2, 2, []), 2)
print(solution(3, 3, []), 6)
print(solution(3, 3, [[2, 2]]), 2)
print(solution(3, 3, [[2, 3]]), 3)
print(solution(3, 3, [[1, 3]]), 5)
print(solution(3, 3, [[1, 3], [3, 1]]), 4)
print(solution(3, 3, [[1, 3], [3, 1], [2, 3]]), 2)
print(solution(3, 3, [[1, 3], [3, 1], [2, 3], [2, 1]]), 1)
print(solution(7, 4, [[2, 1], [2, 2], [2, 3], [4, 2], [4, 3], [4, 4], [6, 2], [6, 3]]), 0) // 이 값이 잘 나오면 테스트1, 테스트9 통과, 위로 가면 안됨
print(solution(4, 4, [[3, 2], [2, 4]]), 7)
print(solution(100, 100, []), 690285631)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 최종 코드
def solution(m, n, puddles):
dp = [[-1 for _ in range(m)] for _ in range(n)]
for puddle in puddles:
dp[puddle[1] - 1][puddle[0] - 1] = 0
for i in range(1,m):
if dp[0][i] == 0:
for j in range(i, m):
dp[0][j] = 0
break
dp[0][i] = 1
for i in range(1, n):
if dp[i][0] == 0:
for j in range(i, n):
dp[j][0] = 0
break
dp[i][0] = 1
dp[0][0] = 0
for i in range(n):
for j in range(m):
if dp[i][j] == -1:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1] % 1000000007
'💡코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 | 파이썬 python] 네트워크 (0) | 2023.05.16 |
---|---|
[프로그래머스 | 파이썬 python] 타겟 넘버 (0) | 2023.05.16 |
[프로그래머스 | 파이썬 python] 정수 삼각형 (0) | 2023.05.16 |
[프로그래머스 | 파이썬 python] 단속카메라 (0) | 2023.04.21 |
[프로그래머스 | 파이썬 python] [크루스칼 알고리즘] 섬 연결하기 (0) | 2023.04.21 |
동적계획법 (Dynamic Programming) | DP
🌏 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 첫 번째 풀이
def solution(m, n, puddles):
dp = [[-1 for _ in range(m)] for _ in range(n)]
dp[0][0] = 0
for i in range(1,m):
dp[0][i] = 1
for i in range(1,n):
dp[i][0] = 1
for puddle in puddles:
dp[puddle[1]-1][puddle[0]-1] = 0
for i in range(n):
for j in range(m):
if dp[i][j] == -1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1] % 1000000007

고딩 때 경우의 수 문제 풀듯이 그림까지 그려가며 코드 짰는데 개같이 실패하였다.
👁 문제점 분석
가로-세로 1열을 1로 채워주었는데 이전에 물웅덩이가 나오면 앞으로 나아갈 수 없으므로
물웅덩이 이후는 0으로 처리해주어야 한다!
👁 반례
질문하기에 천사님이 남겨주신 반례덕분에 문제점을 발견할 수 있었다.
질문하기에 따봉박기가 없는게 너무 아쉽다 하 감사함다 사랑함다❤️
print(solution(2, 2, []), 2)
print(solution(3, 3, []), 6)
print(solution(3, 3, [[2, 2]]), 2)
print(solution(3, 3, [[2, 3]]), 3)
print(solution(3, 3, [[1, 3]]), 5)
print(solution(3, 3, [[1, 3], [3, 1]]), 4)
print(solution(3, 3, [[1, 3], [3, 1], [2, 3]]), 2)
print(solution(3, 3, [[1, 3], [3, 1], [2, 3], [2, 1]]), 1)
print(solution(7, 4, [[2, 1], [2, 2], [2, 3], [4, 2], [4, 3], [4, 4], [6, 2], [6, 3]]), 0) // 이 값이 잘 나오면 테스트1, 테스트9 통과, 위로 가면 안됨
print(solution(4, 4, [[3, 2], [2, 4]]), 7)
print(solution(100, 100, []), 690285631)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 최종 코드
def solution(m, n, puddles):
dp = [[-1 for _ in range(m)] for _ in range(n)]
for puddle in puddles:
dp[puddle[1] - 1][puddle[0] - 1] = 0
for i in range(1,m):
if dp[0][i] == 0:
for j in range(i, m):
dp[0][j] = 0
break
dp[0][i] = 1
for i in range(1, n):
if dp[i][0] == 0:
for j in range(i, n):
dp[j][0] = 0
break
dp[i][0] = 1
dp[0][0] = 0
for i in range(n):
for j in range(m):
if dp[i][j] == -1:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1] % 1000000007
'💡코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 | 파이썬 python] 네트워크 (0) | 2023.05.16 |
---|---|
[프로그래머스 | 파이썬 python] 타겟 넘버 (0) | 2023.05.16 |
[프로그래머스 | 파이썬 python] 정수 삼각형 (0) | 2023.05.16 |
[프로그래머스 | 파이썬 python] 단속카메라 (0) | 2023.04.21 |
[프로그래머스 | 파이썬 python] [크루스칼 알고리즘] 섬 연결하기 (0) | 2023.04.21 |