본문 바로가기

DP10

[백준문제풀이] 2156 포도주 시식 풀이일시 : 2020-12-28 문제 : 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는.. 2021. 1. 4.

[백준문제풀이] 9465 스티커 풀이일시 : 2020-12-28 문제 : 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커.. 2021. 1. 4.

[백준문제풀이] 10844 쉬운 계단 수 풀이일시 : 2020-12-28 문제 : 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 : 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. ex) 2 출력 : 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. ex) 17 풀이 : DP문제이다. 즉 점화식을 세워봐야한다. dbstndi6316.tistory.com/35 [개념정리] DP 동적프로그래밍 Dynamic Programing, DP, 동.. 2021. 1. 4.

[백준문제풀이] 9095 1,2,3더하기 풀이일시 : 2020-10-15 문제 : 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. ex) 3 4 7 10 출력 : 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. ex) 7 44 274 풀이 : DP문제의 기본문제이다. 다이나믹프로그래밍 문제는 .. 2021. 1. 1.

[백준문제풀이] 15852 타일 채우기 3 풀이일시 : 2020-08-09 문제 : 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 입력 : 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 : 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이 : 다이나믹프로그래밍 DP를 이용한다 dbstndi6316.tistory.com/35?category=953970 [개념정리] DP 동적프로그래밍 Dynamic Programing, DP, 동적프로그래밍, 동적계획법 으로 중요한 알고리즘 중 하나이다. DP란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부 dbstndi6316.tistory.com 가장 .. 2020. 12. 29.

[백준문제풀이] 2133 타일 채우기 풀이일시 : 2020-08-09 문제 : 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 : 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 : 첫째 줄에 경우의 수를 출력한다. 풀이 : 가장 마지막에 오는 타일을 생각했을 때 나타나는 경우의 수는 세 가지이다. (그 이전 갯수는 N-2개) 또한 4개이상일 때부터 2의 배수가 될때마다는 고유한 모양이 2개씩 나타난다. D[i] = 3*D[i-2] + (2*D[i-4] + 2*D[i-6] + 2*D[i-8] + .... + 2*D[0]) 아래는 DP에 대한 포스팅이다. 이의 알고리즘으로 풀이했다. dbstndi6316.tistory.com/35?category=953970 [개념정리] DP 동적프로그.. 2020. 12. 29.

[백준문제풀이] 11727 2xn 타일링 2 풀이일시 : 2020-08-09 문제 : 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력: 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 : 점화식을 만들어보자 가장 마지막에 오는 타일을 생각해봤을 때 가능 한 경우의 수를 생각해본다면 1. 1x2 타일 (그 앞엔 N-1개) 2. 2x1 타일 (그 앞엔 N-2개) 3. 2x2 타일 (그 앞엔 N-2개) 점화식 D[i]=D[i-1]+2*D[i-2] 를 도출해 낼 수 있다. DP에 대한 포스팅이다. 점화식을 쓰는것은 이 알고리즘을 사용한것이다. dbstndi6316.tist.. 2020. 12. 29.

[백준문제풀이] 11726 2xn 타일링 풀이일시 : 2020-08-09 문제 : 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력: 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 : 2*n 크기의 직사각형을 1*2, 2*1 타일로 채우는 방법의 수를 구하는 프로그램 작성한다. 가장 마지막에 오는 타일을 기준으로 생각해보았을때 가능한 경우는 오직 두가지이다. -> 1*2 (그전까지는 N-1개) or 2*1 2*1 배치 (그전까지는 N-2개) #include using namespace std; int d[1001]; int dp(int x) { if (x == 1.. 2020. 12. 29.

이전 1 2 다음

티스토리툴바