💡코딩테스트/프로그래머스

[프로그래머스 | 파이썬 python] 등굣길

2023. 5. 16. 15:56
목차
  1. 🌏 문제
  2. 👽 첫 번째 풀이
  3. 👁 문제점 분석
  4. 👁 반례
  5. 👽 최종 코드

동적계획법 (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

 

 

728x90
저작자표시 (새창열림)

'💡코딩테스트 > 프로그래머스' 카테고리의 다른 글

[프로그래머스 | 파이썬 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
  1. 🌏 문제
  2. 👽 첫 번째 풀이
  3. 👁 문제점 분석
  4. 👁 반례
  5. 👽 최종 코드
'💡코딩테스트/프로그래머스' 카테고리의 다른 글
  • [프로그래머스 | 파이썬 python] 네트워크
  • [프로그래머스 | 파이썬 python] 타겟 넘버
  • [프로그래머스 | 파이썬 python] 정수 삼각형
  • [프로그래머스 | 파이썬 python] 단속카메라
두_두
두_두
피할 수 없으면 냅다 즐겨버리기 💚
두_두
왜안되지
두_두
전체
오늘
어제
  • 분류 전체보기 (96)
    • 🌐 웹개발 (30)
      • React (4)
      • 웹 개발 (17)
      • API (3)
    • 💡코딩테스트 (56)
      • 프로그래머스 (49)
      • Leetcode (4)
      • 백준 (3)
    • 📓STUDY (10)
      • 알고리즘 (5)
      • OS (3)
      • 네트워크 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 쉿🤫 두_두는 블로그 이사중🚛

인기 글

태그

  • 그래프
  • leetcode
  • 파이썬
  • nuxt
  • set
  • 코딩테스트
  • react
  • Github
  • BFS
  • 뷰
  • 리액트
  • deque
  • programmers
  • JavaScript
  • DP
  • jQuery
  • 제이쿼리
  • 자바스크립트
  • vue
  • 그리디
  • Python
  • github pages
  • 리트코드
  • JS
  • 코테
  • 프로그래머스
  • 컨텍스트
  • 공룡책
  • dfs
  • 개발

최근 댓글

최근 글

hELLO · Designed By 정상우.
두_두
[프로그래머스 | 파이썬 python] 등굣길
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.