파이썬 알고리즘
3. 돌다리 건너기(Bottom-Up)
도전과제 : 돌다리 건너기(Bottom-Up) 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? ▣ 입력설명 첫째 줄은 돌의 개수인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다. ▣ 입력예제 1 7 ▣ 출력예제 1 34 문제풀이 import sys sys.stdin=open("input.txt", "r") n = int(input()) dy=[0]*(n+2) #dy리스트의 0번 인덱스는 사용하지 않는다. dy[1]=1 dy[2]=2 for i in range(3, n+..
2.네트워크 선 자르기(Top-Down방식)
네트워크 선 자르기(Top-Down : 재귀, 메모이제이션) 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다. 그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요? ▣ 입력설명 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. ▣ 입력예제 1 7 ▣ 출력예제 1 21 문제풀이 impor..
1. 네트워크 선 자르기(Bottom-Up)
네트워크 선 자르기(Bottom-Up) 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다. 그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요? ▣ 입력설명 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. ▣ 출력설명 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. ▣ 입력예제 1 7 ▣ 출력예제 1 21 문제풀이 import sys sys.st..