[Python] 백준 22869번 - 징검다리 건너기

문제 링크 : https://www.acmicpc.net/problem/22869

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

---

문제

 N개의 돌이 일렬로 나열 되어 있다. N개의 돌에는 수 A1A2...Ai...AN로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

1. 항상 오른쪽으로만 이동가능하다.
2.  i번째 돌에서 j(i<j)번째 돌로 이동할 때 (j−i) × (1 + |Ai−Aj|) 만큼 힘을 쓴다.
3. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.

이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자.

입력

첫 번째 줄에 돌의 개수 N와 쓸 수 있는 최대 힘 K가 공백으로 구분되어 주어진다.

두 번째 줄에는 N개의 돌의 수 Ai가 공백으로 구분되어 주어진다.

출력

가장 오른쪽에 있는 돌로 이동할 수 있다면 YES를 출력한다. 만약 이동하지 못하는 경우에는 NO를 출력한다.

예제 입력 :

5 3
1 4 1 3 1

예제 출력 : 

YES

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
stone = list(map(int, input().split()))

dp = [0]*N
dp[0] = 1
for i in range(N-1):
    if dp[i] == 1:
        for j in range(i+1, N):
            if dp[j] == 0 and K >= (j-i)*(1+abs(stone[i]-stone[j])):
                dp[j] = 1
if dp[N-1] == 1:
    print('YES')
else:
    print('NO')

+TMI

난 DP랑 정말 !!! 안맞는 것 같다!! 흑...
이번 문제는 내 머리로 구현은 했는데
바보같이
재귀할 필요 없었는데 재귀로 해서 시간초과가 났다!
그냥 갈 수 있는지 여부만 체크하면 됐는데
온갖 경로를 알고싶었나보다..
쓰읍..

그래서 재귀를 없애니 시간초과는 안뜨는데~~
틀렸습니다...........................
이게 더 속상하다.

그래서 함수로 만들었다가
함수 없애고 그냥 main문으로 때려넣었다가
온갖 짓을 다해봤는데도 틀렸다고 했다...

다른 블로그에 있는 소스랑 비교해봐도 똑같은 것 같았따ㅠㅠ

그런데 달랐음 ㅎ
dp[i] == 1일 때 그 다음 j 반복문을 돌려야했는데
이 if 문 없이 그냥 j로 돌려서 틀렸다고 한 것이었다!!

이런 문제였다니~~
아 그리고
내 소스가 이상한건지 확인해보려고 
블로그의 코드를 제출해봤는데

python3으로 돌리니 시간초과가 뜨고,
pypy3으로 돌리니 맞았다고 떴다!!

그래서 이 차이를 알아보기로 했다.

+ 기억해두기

Python3 vs pypy3

python3은 CPython을 사용한다. 이거는 C와 Python으로 작성된 인터프리터인데
CPython은 python코드를 바이트코드로 컴파일 후에 인터프리터가 실행한다.

반면 pypy3는 Python만을 이용하여 구현한 인터프리터로 프로그램을 실행함과 동시에 바로 컴파일하는 방식이다. 그래서 순수한 python 코드일 경우에 pypy의 속도가 CPython보다 훨씬 빠르다고 한다!
하지만 메모리가 더 많이 사용됨.

장단점이 있기 때문에 코드 상황에 맞추어 적절하게 사용하는 것이 좋다고 한다!

 

속도 및 메모리 차이 후덜덜