본문 바로가기

728x90

알고리즘 문제 풀이/DP19

[백준]14501번: 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp 문제! 크기가 n인 dp 테이블을 만들고 0으로 초기화한다. x일차에 상담을 했을 경우 그 기간동안의 누적수익이 커질 경우에만 dp테이블 값을 증가시켜준다. import sys input = sys.stdin.readline n = int(input()) time = [0]*n price = [0]*n for i in range(n): t, p = map(int,input().split()) time[i] = t price[i] = p dp = [0]*(n+1) for i in range(n): j = i + time[i] wh.. 2023. 3. 23.

[백준]1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 너무너무 dp 문제다 간단하게 문제 예제로 생각해보면 쉽게 이해가 간다 경로합을 저장할 배열을 따로 만들어서 한 층씩 저장한다고 생각해보자. 1층은 당연히 그대로 7일 것이고, 2층은 각각 7+3=10, 7+8=15가 된다 3층 0번째 칸: 10이 그대로 내려와서 10+8=18 1번째 칸: (10,15중 큰 값) + 1 = 15+1 = 16 2번째 칸: 15가 그대로 내려와서 15+0=15 4층 0번째 칸: 18이 그대로 내려와서 18+2=20 1번째 칸: (18,16.. 2023. 3. 11.

[백준]2579번: 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net step: 계단별로 점수를 저장할 배열 dp: 해당 계단을 마지막으로 밟을 때까지 누적된 최고점수를 저장할 배열 계단 규칙 계단은 한 번에 한 칸 또는 두 칸씩 이동할 수 있다. 그러나 연속된 세 개의 계단을 밟을 수는 없다. 위 규칙을 지키면서 i번째 칸을 꼭 밟아야 하는 경우를 생각해보자. 현재 위치한 칸까지 누적된 최고점수 dp[i]를 계산하는 방법은 두 가지가 있다. 1. 직전 칸 밟지 않기 이 경우 .. 2023. 2. 28.

[백준]11053번: 가장 긴 증가하는 부분 수열 / 11722번: 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10.. 2023. 2. 26.

[이코테] 금광 출처: 이것이 취업을 위한 코딩테스트다 with 파이썬 https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 문제 n*m 크기의 금광이 있습니다. 금광은 1*1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. 문제 조건 풀이시간: 30분 시간제한: 1초 메모리제.. 2023. 2. 26.

[이코테] 개미 전사 n = int(input()) arr = list(map(int,input().split())) dp = [0]*n dp[0]=arr[0] dp[1]=max(arr[0],arr[1]) for j in range(2,n): dp[j]=max(dp[j-2]+arr[j],dp[j-1]) print(dp) print(max(dp[n-1],dp[n-2])) 2023. 2. 25.

이전 1 2 3 4 다음

728x90

티스토리툴바