https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 난이도: 실버2 소요시간:20분 inputList[i]가 양수라면 dp[i+1]은 max(dp[i]+inputList[i] , inputList[i])를 하면 된다 이전인덱스의 inputList가 음수였다면 뒤에 것이 맥스 일것이고 양수였다면 앞의 것이 맥스 일것이다. inputList[i]가 음수라면 무조건 전보다 작아진다. 이전의 dp값과 이번 잇풋값을 합쳐서 양수 이면 더하는게 이후에 이득이다. 그러니..
Problem Solving/다이나믹 프로그래밍
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이시간: 1시간이상 걸려서 힌트를 참고하여 품 난이도: 골드5 아래는 나의 코드이다. 처음 접근 법은 자두까 떨어지는 나무가 바뀔때를 기준으로 입력값을 끊어서 생각했다. 예를 들면 2 1 1 2 2 1 1 순으로 자두가 떨어지면 1 2 2 2 로 변환하여서 생각하였다. 이 방법대로 풀어보니 뒤로갈수록 허점들이 발견이 되었고 수정을 하여도 몇몇 케이스에서 제대로 작동을 하지 안았다. 이 접근법 때문에 시간..
이 문제는 이것이 코딩테스트다.226문제이다. 거스름돈 문제와 비슷하지만, 거스름돈은 최소단위의 돈이 있기에 그리디를 사용할 수 있다. 예를 들면 6원을 받았을때 거스름돈 문제는 1원단위의 돈이 있기때문에 어떤경우에도 거스름돈을 줄 수 있다. 하지만 이 문제에서는 1원단위의 돈이없을 수 있다. 그렇기에 다이나믹프로그래밍을 이용하여 풀어야 한다. 아래는 나의 코드이다. import sys moneyNum, moneyVal=map(int,sys.stdin.readline().split()) money=[] for i in range(moneyNum): money.append(int(sys.stdin.readline().rstrip())) money.sort() dp=[-1]*10001 # 초기값 설정 동전화..
이 문제는 이것이 코딩테스트다 223페이지 문제이다. 아래는 나의 코드이다. import sys N= int(sys.stdin.readline().rstrip()) dp=[0]*1001 dp[0]=0 dp[1]=1 dp[2]=3 for i in range(3,N+1): dp[i]=dp[i-1]+ 2*dp[i-2] print(dp[N]%796796) 아래는 예시코드이다. # 정수 N을 입력 받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업) d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i - 1] + 2 * d[..
이것이 코딩테스트다. 220페이지 문제이다. 스키장 3,5,7일권 최저가 구하기 문제와 비슷하다. 다이나믹프로그래밍의 정석 문제 같다. 다이나믹 프로그래밍은 보통 min(나올수있는 경우들) 또는 max(나올 수 있는 경우들)을 이용한다. 이 문제는 바텀업방식문제이다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) food = list(map(int,sys.stdin.readline().split())) dp=[0]*N dp[0]=food[0] dp[1]=max(food[0],food[1]) for i in range(2,N): dp[i] = max(dp[i-2]+food[i],dp[i-1]) print(dp) print(dp[N-1]) 아래는..
이 문제는 이것이 코딩테스트다. 217페이지 문제이다. 문제 난이도는 높지 않았다. 아래는 나의 코드이다. import sys N=int(sys.stdin.readline().rstrip()) dp=[0]*(N+1) dp[1]=0 dp[2]=1 for i in range(2,N+1): temp = [N] * 4 if i%5 == 0: temp[0] = dp[i//5] + 1 if i%3 == 0: temp[1] = dp[i//3] + 1 if i%2 == 0: temp[2] = dp[i//2] + 1 temp[3]=dp[i-1]+1 dp[i]=min(temp) print(dp[N]) 아래는 예시코드 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 ..
