본문 바로가기

동적 프로그래밍14

[백준] 동적 프로그래밍 - 12865번 평범한 배낭(Java) 문제링크 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 처음에 1차원 배열로 계산하여.. 실패하였다.. 다른 블로그들을 보며 아래 소스코드 작성 방법을 참조하여 문제를 풀었다. 소스코드 작성 방법 a를 이중 배열로 선언 크기는 [n+1][k+1]로 i는 물건의 종류, j는 무게 a[i][j]에 i-1번째 물품을 넣었을 때의 가치를 넣음 (현재(j) 무게 - 물품의 무게) > 0 이라면 max(i번째 물건을 .. 2020. 12. 6.
[백준] 동적 프로그래밍 - 11051번 이항 계수 2 (Java) 문제링크 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 처음에는 예를 들어, $_{5}C_{2}$를 구한다 했을 때 $_{4}C_{0}$을 가장 먼저 구한 다음 차례 차례 조합 공식에 맞추어 $_{5}C_{1}$을 구하고 마지막 최종값을 구하도록 짰는데 틀렸다... 결국... 다른 분들의 블로그 도움을 받았다 T^T 이 문제는 파스칼의 삼각형을 이용하는 문제였다. (된장...ㅎㅎㅎ 언제 배웠는지도 기억이 안나는 데.. 이 이론을 기억할리가 있나 ㅎㅎㅎㅎ) 파스칼의 삼각형 이론 참조 링크 파스칼의 삼각형의 이론을 요약하여 예를 들면, 아래와 같.. 2020. 12. 1.
[백준] 동적 프로그래밍 - 11057번 오르막 수 (Java) 문제링크 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 아래 문제를 고군분투하며 풀고나니 이 문제는 쉽게 풀 수 있었다. 출처 : 2020/11/29 - [알고리즘/동적 프로그래밍] - [백준] 동적 프로그래밍 - 10844번 쉬운 계단 수 (Java) 끝자리가 0일 경우 : 앞자리에 0만 올 수 있다. (00) 끝자리가 1일 경우 : 앞자리에 0, 1 두가지가 올 수 있다. (01, 11) 끝자리가 2일 경우 : 앞자리에 0, 1, 2.. 2020. 11. 29.
[백준] 동적 프로그래밍 - 10844번 쉬운 계단 수 (Java) 문제링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이 방법 n=4일 때까지, 전부 나열해보고 규칙을 찾아보려 했지만 전혀 보이지 않았다. 앞자리가 0, 9일 때 다음 자릿수에 올 수 있는 건 한가지뿐이어서 각 n자리수마다 0과 9의 갯수를 세서 규칙을 찾아보려했지만, 발견하지 못했다. 그래서 다른 블로그들의 글을 보고.. 해결하였다. 끝자리가 0일 경우 : 앞자리에 숫자 1만 가능하다. (한가지) 끝자리가 1~8일 경우 : 끝자리를 i라고 한다면 앞자리에 숫자 i-1, 숫자 i+1 이 가능하다. (두가지) e.g. 끝자리가 1이라면 앞자리에 0, 2가 가능하다. 끝자리가 9일 경우 : 앞.. 2020. 11. 29.
[백준] 동적 프로그래밍 - 11052번 카드 구매하기 (Java) 문제링크 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 아래 문제를 응용하여 풀이방법을 생각해보았다. 출처 : 2020/11/10 - [알고리즘/이것이 코딩테스트다] - Chapter 08 동적 프로그래밍 - 효율적인 화폐 구성 (java) $p_{0,i}$ : 카드 i개가 포함된 카드팩의 단위 $p_{1,i}$ : 카드 i개가 포함된 카드팩의 가격 $a_{j}$ : 카드 j개를 갖기 위해 지불할 수 있는 최대 금액 $a_{j-p_{0,i}}$ : 카드팩에 단위를 $p_{0,i}.. 2020. 11. 28.
[백준] 동적 프로그래밍 - 1699번 제곱수의 합 (Java) 문제링크 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이 방법 이 문제를 며칠을 고민했는지 모른다 ㅠㅠ 결국, 다른 분들의 블로그 풀이를 보고 겨우.... 이해했다... 이해 잘 된 거겠지... 규칙을 찾기 위해 아래와 같이 나열하고, 그에 따른 점화식을 세워보자. $a_{n} = min(a_{n- {1}^{2}} + 1, a_{n-{2}^{2}} + 1 , ... , a_{n-{i}^{2}} + 1)$ ${i}^{2}$ 은 n보다 작은.. 2020. 11. 21.
[백준] 동적 프로그래밍 - 2294번 동전 2 (Java) 문제링크 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 접근한 방법 동적 프로그래밍 문제 풀이 방법 $a_{i}$ : 금액 i를 만들 수 있는 최소한의 화폐 개수 $a_{i-k}$ : 화폐의 단위를 k라고 했을 때, 금액 (i-k)를 만들 수 있는 최소한의 화폐 개수 (i-k : 금액 i에서 화폐의 단위 k를 뺀 금액) 이 문제를 점화식으로 표현해보면 아래와 같다. $a_{i-k}$를 만드는 방법이 존재 O $a_{i} = min(a_{i}, a_{i-k}+1)$ 화폐 단위 작.. 2020. 11. 21.
[백준] 동적 프로그래밍 - 1904번 01타일 (Java) 문제링크 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이 방법 일단, 규칙을 찾는 데 집중하여 아래 표와 같이 그려보며 규칙을 발견하였다. N-1자리 끝에는 1을 붙이고, N-2자리 끝에는 00을 붙여서 N자리 수를 만들 수 있다. $a_{n} = a_{n-1} + a_{n-2}$ $a_{n}$ 나열 개수 $a_{1}$ 1 1 $a_{2}$ 11 00 2 $a_{3}$ 111 001 100 3 $a_{n}$ 1100 0000 1111 0011 1001 5 소스코드 작성 방법 a배열.. 2020. 11. 21.
[백준] 동적 프로그래밍 - 2193번 이친수 (Java) 문제링크 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이방법 일단, 규칙을 찾는 데 집중했고 아래와 같은 규칙을 발견하였다. N-1자리 이친수의 끝자리가 0이냐 1이냐에 따라 N자리 이친수의 개수가 정해진다. N-1자리 이친수의 끝자리가 0이면 0과 1을 더 붙일 수 있다. N-1자리 이친수의 끝자리가 1이면 0만 붙일 수 있다. 따라서, 점화식을 세워보면 아래와 같다. $a_{n,0}$ : n자리 이친수 중 끝자리가 0인 개수 $a_{n,1}$ : n자리 이친수 .. 2020. 11. 20.
[백준] 동적 프로그래밍 - 9465번 스티커 (Java) 문제링크 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 접근한 방법 동적 프로그래밍 풀이 방법 2행이므로 열마다의 경우의 수를 고려해보면 된다. 열 하나에서 생각해볼 수 있는 경우의 수는 아래와 같이 3가지이다. 왼쪽부터 탐색 0 1 2 X O X X X O X : 스티커를 뜯지 않음 | O : 스티커를 뜯음 이를 토대로 a[경우의 수 인덱스(크기 3)][스티커 열의 인덱스(크기 n)] 배열로 점화식을 세운다. 편의상 $a_{i,col}$라 하자. $a_{i,col}$ : col열의 i경우에 따라.. 2020. 11. 12.
[이.코.테] Chapter 08 동적 프로그래밍 - 효율적인 화폐 구성 (java) 효율적인 화폐 구성 문제 (교재 99p) 난이도 ●●○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화페는 몇개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 입출력 조건) 입력 조건 - 첫째 줄에 N, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 10,000) - 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다. 출력 조건 - 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다. - 불가능할 때는 -1을 출력한다. 입출력 예시) 입력 예시 출력.. 2020. 11. 10.
[이.코.테] Chapter 08 동적 프로그래밍 - 바닥공사 (java) 바닥공사 문제 (교재 223p) 난이도 ●◐○ | 풀이 시간 20분 | 시간 제한 1초 | 메모리 제한 128MB 문제가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 입출력 조건) 입력 조건 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000) 출력 조건 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력한다.첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. 입출력 예시) 입력 예시 출력 예시 3 5 문제 풀이 방법 - .. 2020. 11. 6.
반응형

티스토리툴바