[백준] 22869번: 징검다리 건너기 small (파이썬/Python) - DP

2022. 12. 10. 14:24·Algorithm (PS)
728x90

https://www.acmicpc.net/problem/22869

 

22869번: 징검다리 건너기 (small)

$N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으

www.acmicpc.net

징검다리 건너기 (large) 문제와 거의 동일하게 풀었다. 
다만 마지막에 dp[-1] 칸이 값이 k보다 작거나 같은지 확인해주면 된다. 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
array = list(map(int, input().split()))
INF = int(1e9)
dp = [INF]*n # i 번째까지 올때 드는 최대힘
dp[0] = 0
for i in range(1, n):
    for j in range(0, i):
        cost = max((i-j) * (1+abs(array[i]-array[j])), dp[j]) # i 번째 돌에서 j 번째돌로 이동할 때의 비용
        if cost <= k:
            dp[i] = min(cost, dp[i])

if dp[-1] <= k:
    print("YES")
else:
    print("NO")
728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 14567번: 선수과목 (Python/파이썬) - 위상정렬  (0) 2022.12.11
[백준] 13913번 : 숨바꼭질 4 (파이썬/Python) - BFS 풀이  (0) 2022.12.10
[백준] 20444번: 색종이와 가위 (파이썬/Python) - 이진탐색  (0) 2022.12.09
[백준] 20164번 : 홀수 홀릭 호석 (파이썬/Python) - 구현, 브루트포스  (0) 2022.12.09
[백준] 1253번 : 좋다 (파이썬/Python)  (0) 2022.12.09
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 14567번: 선수과목 (Python/파이썬) - 위상정렬
  • [백준] 13913번 : 숨바꼭질 4 (파이썬/Python) - BFS 풀이
  • [백준] 20444번: 색종이와 가위 (파이썬/Python) - 이진탐색
  • [백준] 20164번 : 홀수 홀릭 호석 (파이썬/Python) - 구현, 브루트포스
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • 프로그래머스
  • 스파크
  • EC2
  • 운영체제
  • Kubernetes
  • 카카오코딩테스트
  • 백준
  • Leetcode
  • 빅데이터
  • docker
  • dfs
  • 클라우드
  • 쿠버네티스
  • 파이썬
  • python
  • ansible
  • 데이터엔지니어링
  • BFS
  • SPARK
  • Swift
  • 알고리즘
  • 데이터브릭스
  • Databricks
  • 코딩테스트
  • AWS
  • 리눅스
  • dp
  • 데이터엔지니어
  • linux
  • 백트래킹

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[백준] 22869번: 징검다리 건너기 small (파이썬/Python) - DP
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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