DP
-
(백준 10844번 쉬운 계단의 수 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 8PROGRAMMING/알고리즘 2024. 3. 14. 08:16
출근 전 한문제 컷! 이라고 말하기엔 그제부터 풀었던 쉬운 계단의 수 문제 ㅎㅎ 백준 10844번 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이는 간단하다!(라고 말하고 생각하는데 하루 걸렸다) f(n)을 n자리 계단수의 갯수라고 정의하면 f(n+1) = 2 * f(n) - {n자리 계단수 중 마지막 자리가 0또는 9인 수의 갯수}로 나타낼 수 있다. 마지막 자리가 0 또는 9인 수를 알기 위해 DP[n][10]을 만들어 기록해주기만 하면 완성! 마지막 자리수가 1인 수만이 그 다음 숫자의 마지막 수를 0으로 만들 수 있고, 마지막 자리수가 8인 수만..
-
(백준 12865번 평범한 배낭 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 7PROGRAMMING/알고리즘 2024. 3. 14. 00:06
오늘은 배낭 문제를 풀어보았다. 회사갈 때 재미로 코딩테스트 푸는 영상을 보는데, 문제를 읽다보니 어제 본 문제랑 똑같았다!!!! 아래 유튜브 아니였으면 평생 못 풀고 이해도 못했을텐데..😖 영상이 진짜 잘 설명해준다!!!!(강추) https://www.youtube.com/watch?v=rhda6lR5kyQ 백준 12865번 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이..
-
(백준 11052번 카드 구매하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 4탄PROGRAMMING/알고리즘 2024. 3. 12. 08:16
한달만에 복귀했다ㅎㅎ 이번주 DP 예제문제 다 뽀개고 다음 알고리즘으로 고고!! 백준 11052번 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 자체는 어렵지 않다. f(n)을 n개의 카드에 사는데 드는 최대의 금액이라고 정의하면 f(n)은 f(n-1) + (1개의 카드에 지불할 최대 금액), f(n-1) + (2개의 카드에 지불할 최대의 금액), ... ,(f(1) + (n-1)개의 카드에 지불할 최대의 금액) 중 가장 큰 금액이 된다. 그러..
-
(백준 11726번/11727번 2*n 타일링 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 2탄PROGRAMMING/알고리즘 2024. 1. 19. 18:13
기세를 몰아! 디피디피~ 백준 11726번 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 잘 생각해보면 n번째 케이스는 n-1 번째 케이스에서 직사각형을 세로로 세워 붙인 경우와 n-2번째 케이스에서 직사각형을 눕혀서 2개 붙인 경우의 합으로 이루어졌음을 알 수 있다. // 백준 11726번 #define _CRT_SECURE_NO_WARNINGS #include #include const long long MAX = 1001; long long dp[MAX]; ..
-
(백준 2193번/1904번 이친수/01타일 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법PROGRAMMING/알고리즘 2024. 1. 19. 17:11
DP만 잘 알아도 코테가 쉬워진다는 말을 어디서 들은 적이 있는뎁...!ㅎㅎ 라이님 블로그를 보면서 실력을 키워보쟈! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777103650&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 동적 계획법(Dynamic Programming) (수정: 2019-02-07) 안녕하세요. 오늘 소개해 드릴 것은 바로 그 유명한 다이나믹 프로그래밍(Dynamic Programming)입니다. ... blog.naver.com 🚨위 블로그에 있는 문제(1463번 1로 만들기, 9465번 스티커, 2294번 스티커)는..