[코딩테스트] 프로그래머스 - 등굣길

2024. 3. 28. 22:27·코딩테스트
목차
  1. 1. 아이디어 
  2. 2. 시간복잡도
  3. 3. 변수
  4. Code

1. 아이디어 

▪ dp 알고리즘으로 구현 

▪ (i,j) 좌표로 가는 경로의 수는 다음의 점화식을 따름 -> dp[j][i] = dp[j-1][i] + dp[j][i-1]

▪ 경로의 수를 저장할 dp 리스트 0으로 초기화, 시작점인 (1,1)은 1로 초기화

▪ 2중 for문 돌면서 경로의 수 리스트 채우기 

   - (1,1)인 경우 skip

   - (i,j)가 물에 잠긴 경우 해당 좌표로 가는 경로의 수는 0 

   - (i,j)로 가는 경로의 수는 (i-1,j)로 가는 경로의 수와 (i,j-1)로 가는 경로의 수를 더한 값에 % 1000000007

▪ dp의 마지막 행, 마지막 열 값 return 

2. 시간복잡도

▪ O(n*m)

3. 변수

▪ 경로의 수를 저장할 리스트: int[][]

Code

def solution(m, n, puddles):
answer = 0
dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1
for j in range(1,n+1):
for i in range(1,m+1):
if i == 1 and j == 1:
continue
if [i,j] in puddles:
dp[j][i] = 0
else:
dp[j][i] = (dp[j-1][i] + dp[j][i-1]) % 1000000007
answer = dp[n][m]
return answer
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

'코딩테스트' 카테고리의 다른 글

[코딩테스트] 프로그래머스 - 단속카메라  (1) 2024.03.29
[코딩테스트] 프로그래머스 - 숫자 게임  (1) 2024.03.29
[코딩테스트] 프로그래머스 - 최고의 집합  (0) 2024.03.28
[코딩테스트] 프로그래머스 - 단어 변환  (0) 2024.03.27
[코딩테스트] 프로그래머스 - 야근 지수  (0) 2024.03.27
  1. 1. 아이디어 
  2. 2. 시간복잡도
  3. 3. 변수
  4. Code
'코딩테스트' 카테고리의 다른 글
  • [코딩테스트] 프로그래머스 - 단속카메라
  • [코딩테스트] 프로그래머스 - 숫자 게임
  • [코딩테스트] 프로그래머스 - 최고의 집합
  • [코딩테스트] 프로그래머스 - 단어 변환
Doodo
Doodo
  • Doodo
    Doodo
    Doodo
  • 전체
    오늘
    어제
    • 분류 전체보기 (192)
      • CS (17)
        • Network (11)
        • Database (6)
      • Language (19)
        • Python (11)
        • SQL (6)
        • R (2)
      • Linux (17)
      • DevOps (35)
        • Git (7)
        • Docker (8)
        • Kubernetes (9)
        • GCP (4)
        • AWS (7)
      • Data Engineering (50)
        • 책 리뷰 (14)
        • Airflow (35)
        • Redis (1)
      • DBMS (21)
        • CUBRID (21)
      • ML & DL (2)
      • 코딩테스트 (24)
      • 프로젝트 (7)
        • 서울시 대기현황 데이터 적재 프로젝트 (4)
        • CryptoStream (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Doodo
[코딩테스트] 프로그래머스 - 등굣길
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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