알고리즘 (2020 : 08 : 10 ~ )/다이나믹 프로그래밍 (43) 썸네일형 리스트형 [백준 / BOJ] 14699 관악산 등반 - Swift 문제 출처 : www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net N개의 쉼터가 있고, 쉼터둘을 연결하는 M개의 도로가 있다. 각 쉼터에는 높이가 있으며, 항상 현재쉼터보다 높은위치로만 갈수있다고할때, 각 쉼터에서 최대한으로 방문할수있는 쉼터의 갯수를 구하는 문제다. 풀이 전에 풀었던 Dp+DFS문제인 욕심쟁이 판다 : www.acmicpc.net/problem/1937 와 비슷한 유형?의 문제라고 생각했다 *항상 현재 쉼터 보다 높은 쉼터로만 .. [백준/BOJ] 11560 다항식 게임 문제 출처 : www.acmicpc.net/problem/11560 11560번: 다항식 게임 매 테스트 케이스마다 한 줄에 걸쳐 다항식 \(p(x) = (1+x)(1+x+x^2)(1+x+x^2+x^3)\dots(1+x+\dots+x^{k-1}+x^k)\)의 \(x^N\)항의 계수를 출력한다. www.acmicpc.net k에 따라 다항식이 연결된다. k = 0 (1) k = 1 (1)(1+x) k = 2 (1)(1+x)(1+x+x^2) k = 3 (1)(1+x)(1+x+x^2)(1+x+x^2+x^3) . . . k = ? 일때의 다항식을 계산한 결과에서 N차항의 계수를 출력하는 문제다. 풀이 k = 20 , N = 210까지 간다. k가 늘어남에따라, 곱해야하는 항의 차수 또한 매우 늘어나므로, 완탐으.. [백준 / BOJ] 14720 우유 축제 문제 출처 www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후�� www.acmicpc.net 영학이는 딸기우유 초코우유 바나나 우유를 좋아한다. 영학이는 가게를 지나가면서 우유를 먹을건데, 무조건 딸기우유 초코우유 바나나우유 순서로 먹어야한다. (초코우유를 먹지않고, 딸기우유만 먹었다면 바나나 우유를 먹지못한다.) 이때, 영학이가 먹을수있는 우유의 최대 갯수를 구하는문제다. 풀이 딸기우유 : 0, 초코유우 : 1, 바나나우유 : 2 라 할때 영학이가 우유를 먹기 시작할수있는 위치는 0이다.(.. [백준 / BOJ] 11062 카드게임 문제 출처 : www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 � www.acmicpc.net 근우와 명우는 카드게임을 하고있다. 근우부터 시작하여 번갈아가면서 카드를 선택하는데, 이때 서로가 최선의 전략으로 임할때 근우가 얻는 최대점수를 구하는문제다. (단, 남아있는 카드중 가장 오른쪽과 가장끝만 선택할수있다.) 풀이 어려웠던 문제였다. 서로가 항상 최선의 전략으로 임한다고 하는데, 어떤 걸 선택해야 최선의 상황이 되는지 모르기 때문에 모든경우를 다 봐줘야한다. 플레이어(근우와 명우)는 .. [백준 / BOJ] 2313 보석 구매하기 출처 풀이 : www.acmicpc.net/problem/2313 2313번: 보석 구매하기 첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 2×n개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 ≤ L ≤ 1,000)이 주어지고, 그 다음 줄에 www.acmicpc.net 보석가게에 보석이 여러줄에 걸쳐 진열되어있다. 각각의 보석은 정수로 표현된다. 이때 음수도 나올수있다. 보석은 연속해서 구매할수있는데, 1 2 3을 구매할수있지만, 1 3 을 구매하지 못한다. 보석 가치의 총합이 최대가 될때를 찾아는 문제다. 풀이 한줄당 최대 1000개의 보석이 있을수있고, 최대 1000개의줄이 나올수있다. 따라서 최대 보석은 1000000개 만.. [백준 / BOJ] 2611 자동차 경주 문제 출처 : www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net N개의 지점이 있는 그래프가 주어진다. 각 지점사이를 연결하는 도로에는 그 도로를 지날때 얻는 점수가 있다. 1번지점에서 출발해서 다시 1번지점으로 돌아올때, 가장 많이 얻을수있는 점수와, 그때의 경로를 출력하는 문제다. 도로는 단방향 이다. 풀이 dp배열에 (dp[idx] = idx까지 도착했을때 얻은 최대 점수) 를 저장해준다. DFS를 돌리며, dp[현재 도로에 도착했을때 까지 얻은.. [백준 / BOJ] 17485 진우의 달 여행 (Large) 문제 출처 : www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 진우가 지구에서 출발해서 달에 도착했을때, 필요한 자금을 최소화 하는문제다. 달에서 지구까지 가는길에 각 칸에 자금이 주어진다. 풀이 N,M이 각각 최대 1000이고, 한 인덱스에서 아래로 갈수있는방향이 3가지 (왼쪽아래 오른쪽아래 중간) 이므로 완전탐색으로 풀려고하면 시간초과가 난다. 다이나믹 프로그래밍으로 풀어야 했는데, dp배열을 구현하고 사용하는게 힘.. [백준 / BOJ] 2410 2의 멱수의 합 문제 출처 : www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 자연수 N을 입력받았을때, 그 자연수를 2의 멱수의 합으로 나타내는 경우의수를 구하시오 예를들어 3 1 + 1 + 1 1 + 2 두가지 경우로 나타낼수있다. 풀이 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력받은 동전들을 .. 이전 1 2 3 4 5 6 다음
