[백준] Python,Java로 풀기📖/다이나믹
백준 1932(정수 삼각형) - Python(파이썬) -DP
백준 1932(정수 삼각형) - Python(파이썬) -DP
2022.07.071932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 예제 풀이 j=0 j=1 j=2 j=3 j=4 dp[0] dp[0][0] = 7 dp[1] dp[0][0] +dp[1][0] = 7 + 3 = 10 dp[0][0] +dp[1][1] = 7 + 8 = 15 dp[2] dp[1][0] +dp[2][0] = 10 + 8 = 18 max( dp[1][0]+dp[2][1], dp[1][1]+dp[2][1] ) = max(11,16) =16 dp[1][1] +dp[2][2] = 15 + 0 = 15 dp[3] dp[2][0] +dp[3][0] = 18 + 2 = 20 max( dp[2][0]+..
백준 11054(가장 긴 바이토닉 부분 수열) - Python(파이썬),Java(자바) - DP
백준 11054(가장 긴 바이토닉 부분 수열) - Python(파이썬),Java(자바) - DP
2022.07.0611054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 예제 풀이 가장 긴 바이토닉 부분 수열이 되기 위해서는 1 2 3 4 5 2 1 이 경우가 가장 기므로 출력으로 7이 나오게된다. 이걸 dp로 해석하면 증가하는지 dp로 확인하기 1) dp[1] = 5 전 수열 증가하는지 확인 결과 1 5 2 1 4 3 4 5 2 1 1 2 1 1 1 1 1 1 1 1 2) dp[2] = 2 전 수열 증가하는 지 확인 1 5 2 1 4 3 4 5 2 1 1 2 2 1 1 1 1 1 1 1 2) dp[3] = 1 전 수열 증가하는 지 확인 1 5 2 ..
백준 10844(쉬운 계단 수) - Python(파이썬) - DP
백준 10844(쉬운 계단 수) - Python(파이썬) - DP
2022.07.0510844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 예제 풀이 일단 첨에 보고 이해가 안되었다. 문제 뜻은 이와 같다 계단 같은 경우에는 무조건 +1 , -1 차이가 난다는 것이다. 자릿수가 1인 수를 구하라고 하면 1 - 9 이렇게 9개가 존재한다라는 의미이다. 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 자릿수가 2인 수를 구하라고 하면 0 _ -> 1개(1) , 1 _ -> 2개(0,2) , 2 _ -> 2개(1,3) , 3 _ -> 2개(2,4) , 4 _ -> 2개(3,5) , 5 _ ->2개(4,6) , 6 _ -> 2개(5,7) , 7 _ -> 2개(6,8) , 8 _ -> 2개(7,9) ..
백준 2579(계단 오르기) -Python(파이썬),Java(자바) - DP
백준 2579(계단 오르기) -Python(파이썬),Java(자바) - DP
2022.07.012579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 예제 풀이 마지막 계단(i=5)에서의 최댓값이 나오는 가지수는 다음과 같다 1️⃣ i=2(5-3)일때의 최댓값 + ( i=4 ) + ( i=5 ) 2️⃣ i=3(5-2)일때의 최댓값 + ( i=5 ) 이 두가지를 비교해서 최댓값을 구하면 된다. dp[i] 0 1 2 3 4 5 i번째일 때의 최댓값 10 10+20 =30 10+15,20+15 중 큰 값= 35 dp[3-3]+(i=2)+ (i=3), dp[3-2]+(i=3) 중 큰 값 = 55 dp[4-3]+(i=3)+ (i=..
백준 9095(1,2,3 더하기) - Python(파이썬)
백준 9095(1,2,3 더하기) - Python(파이썬)
2022.06.309095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net * 내가 생각한 풀이 * 예제 풀이 dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] dp[7] dp[8] dp[9] dp[10] 1 dp[1] +dp[2] =2 dp[1] +dp[2] +dp[3] =4 dp[1] +dp[2] +dp[3] =7 dp[2] +dp[3] +dp[4] =13 dp[3] +dp[4] +dp[5] =24 dp[4] +dp[5] +dp[6] =44 dp[5] +dp[6] +dp[7] =81 dp[6] +dp[7] +dp[8] =149 dp[7] +dp[8] +dp[9] =274 💻 Python(파이썬) import sys ..
백준 1463(1로 만들기) - Python(파이썬) - 다이나믹
백준 1463(1로 만들기) - Python(파이썬) - 다이나믹
2022.06.291463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 예제 풀이 2-> dp[1]+1,dp[2//2]+1 -> min(1,1)=1 10 -> 3이 나오게 된다. dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] dp[7] dp[8] dp[9] dp[10] 0 0 (dp[1]+1,dp[2//2]+1) = (1,1) = 1 (dp[2]+1,dp[3//3]+1) = (2,1) = 1 (dp[3]+1,dp[4//2]+1) = (2,2) = 2 (dp[4]+1) = 2 (dp[5]+1,dp[6//2]+1,dp[6//3]+1) = (3,2,2) = 2 dp[6]+1 = 3 (dp[7)+1,dp[8//2]+1) = ..
백준 1495(기타리스트) - Python(파이썬),Java(자바) - 다이나믹 프로그래밍
백준 1495(기타리스트) - Python(파이썬),Java(자바) - 다이나믹 프로그래밍
2022.06.231495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 예제 풀이 1) 시작 볼륨(S)= 5일 바꿀 수 있는 볼륨 -> 0 , 10 => 5-v[0] = 0 or 5+v[0] = 10 0 1 2 3 4 5 6 7 8 9 10 1 1 2) 현재 볼륨이 0과 10인 경우 바꿀 수 있는 볼륨 -> 3 , 7 => 0-v[1] = -3(0보다 작으므로 X) or 0+v[1] = 3 or 10-v[1] = 7 or 10+v[1] = 13(최댓값 10보다 크므로 X) 0 1 2 3 4 5 ..
백준 1890(점프) - Python(파이썬) - 다이나믹
백준 1890(점프) - Python(파이썬) - 다이나믹
2022.06.201890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음 생각한 풀이는 다이나믹 프로그래밍이아니라 DFS를 생각해서 풀었다. 근데 시간제한에 걸리는걸로봐서 다이나믹 프로그래밍으로 다시 풀었다. 예제 설명 ① dp 테이블로 모두 다 0을 만들기 첫번째 줄 ( i=0 ) ② dp 테이블 가장 왼쪽 위 칸(dp[0][0]) =1 ③ array 테이블에서 array[0][0]의 값이 2이므로 오른쪽 +2 -> dp[0][0+2] = dp[0][0]+dp[0][2] 아래쪽 +2 -> dp[0+2][0] = dp..
백준 20152(Game Addiction) - Python(파이썬) - 다이나믹
백준 20152(Game Addiction) - Python(파이썬) - 다이나믹
2022.06.0620152번: Game Addiction 첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다. www.acmicpc.net 예제 설명 (8,8) -> (4,4) 를 가는 방법의 수는 (4,4) -> (8,8) 로 가는 방법의 수랑 동일하다. 이 방법의 수는 y>x인 곳은 침수되어서 갈 수 없다고 하였으므로 (4,5),(4,6),,, 이 모든 값은 0이라고 볼 수 있다. (4,4)의 점을 (0,0)이라고 가정하고, (8,8)의 점을 (4,4)라고 가정하고나서 표를 작성하면 다음과 같다 점화식 | if j>=i : dp[j][i] = dp[j-1][i] + dp[j][i-1] j \ i 4=0 5=1 6=2 7=3 8=4 4..
백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹
백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹
2022.06.02문제 설명 이런 원리로 (2,1)의 점 1, (3,1)의 점 1, (2,2)의 점 3이 세점을 더해서 5가 만들어지는 것이다. 즉 , 5 (3,2) = 1(2,1) + 1(3,1) + 3(2,2) 이걸 dp 그래프안에 넣었다고 가정해서 점화식으로 풀면 dp[m][n] = dp[m-1][n-1]+dp[m-1][n] + dp[m][n-1] 풀이 방법 ① m=1, n = 1인 지점은 모두 1이다. 갈 수 있는 방법은 무조건 일이다 1 1 1 1 1 1 1 ② 따라서 m의 값이 증가에 따라 for문 해서 1부터 n까지 루프문 돌린다. ③ 단, 수가 커지기 때문에 array값을 구할 때 마다 1,000,000,007 나눈 나머지 값을 구한다. Python(파이썬) import sys n,m = map(int,sy..
백준 2096(내려가기) - Python(파이썬) - 다이나믹 프로그래밍,메모리 초과
백준 2096(내려가기) - Python(파이썬) - 다이나믹 프로그래밍,메모리 초과
2022.05.302096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net ※ 이 문제의 경우 메모리 초과를 조심해야한다. 배열을 막 선언할 경우 메모리 초과가 날 수 있다 ※ 또, 파이썬의 경우 =으로 복사할 경우 같은 곳을 참조하여서 문제가 될 수 있다. 따라서 copy()를 이용하여서 복사한다. 풀이방법 ① dp_max,dp_min을 선언하는데 이때 첫째줄 한줄만 입력 받는다. ② for문으로 그 담줄부터 입력받으므로 1부터 N전까지 입력받아서 a,b,c로 입력받는다. ③ 앞에 있었던 dp_max의 0번째 항에는 dp_max의 0번째항과 1번째..
백준 2502(떡 먹는 호랑이) - Python(파이썬) - 다이나믹프로그래밍
백준 2502(떡 먹는 호랑이) - Python(파이썬) - 다이나믹프로그래밍
2022.05.302502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 접근방법 일단 1, 2, 3, 5 이런식으로 증가하기 때문에 피보나치 수열인 것을 안다. 이걸 문자로 표현하여서 첫째와 둘째를 A와 B라고 가정하면 밑의 표와 같이 증가한다. 1 2 3 4 5 6 7 A B A+B A+2B 2A+3B 3A+5B 5A+8B 이걸 A의 계수 관점, B의 계수 관점으로 분리하면 A의 계수 관점(dpA) 1 2 3 4 5 6 7 1 0 1 1 2 3 5 B의 계수 관점(dpB) 1 2 3 4 5 6 7 0 1 1 2 3 5 8..