algorithm/dp

입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000 이하의 자연수이다. 풀이 입력조건에 중요한 단서가 있다. 계단에 써져 있는 수는 모두 자연수다. 즉, 계단은 밟을 수 있다면 밟는게 일단 이득이라는 뜻이다. 하지만 3연속으로 밟을 수는 없으니 더 큰 점수를 위해 때로는 연속으로 가지 말아야 한다. 계단에 각 숫자가 몇이 써져 있는지 나와있는 입력배열을 arr [n] n번째 계단까지 올랐을 때 얻게 되는 점수의 최댓값 배열을 sum [n]이라고 하자. sum [n]은 1. sum [n-2]+arr [n] (n-2번째 계단의 최대..

풀이 명백한 공식을 찾기는 어려워 보인다. 하지만 하위 개수 경우가 상위 개수에 영향을 끼치는 것 같다. 바로 생각이 나지 않을 때는, 한번 나열해 보자. N=2일 때: 11,00 2가지 경우가 있다. N=3일 때: 001, 100, 111 3가지 경우가 있다 N=4일 때: 0000,0011,1001,1100,1111 5가지 경우가 있다. N=5일 때: 00001,10000,00100,00111,10011,11001,11100,11111 7가지 경우가 있다. 피보나치수열처럼 이전 두 항의 합이 다음 항의 값이 되는 것처럼 보인다. 왜 그럴까? 길이가 N인 수열을 만든다고 가정하자. 이전 N-1번째나 N-2번째 수열은 그 사이에 숫자를 삽입하지 않고 뒤에만 숫자를 붙인다고 가정할 수 있다. 이는 N-1번째..

풀이 일단 2보다는 3으로 나누는게 더 숫자를 작게 만들 수 있어보인다. 그렇다면 일단 3의 배수가 될때 까지 1을 뺀후 3으로 나누면 되는 것일까? 하지만 그렇게 하면 8같은 경우 3으로 나누는 것만 추구하면: 8->7->6->2->1 로 5회 2로만 나누면: 8->4->2->1로 4회 로 2로만 나눈 값이 더 작다. 즉, 고정된 공식이 명백히 더 빠르다는 것을 보장해 줄 수 없다. 명백한 공식이 없다면 결국 경우를 빠르게 계산 해야 한다. 그 경우를 모두 빠르게 제시하는 과정에서 동적 프로그래밍을 사용한다. 이 문제는 동적 프로그래밍 문제다. 차근차근 낮은 값들을 바탕으로 높은 값을 추론해내면 되는 것이다. 정수를 받아 그 길이 보다 1만큼 큰 배열을 만든다. 배열에 배열의 인덱스가 1에 도달하는 연..

풀이 일단 출력할 수 없는 경우 먼저 생각하자. 사고의 순서를 써보자 1.가장 봉지수가 적은 경우를 찾아야 한다. 2.그러기 위해서는 가능한 5kg 봉투를 많이 사용해야 한다. 3.그렇다면 3kg 봉투는 최소로 사용해야 한다. 4.그렇다면 3kg 봉투는 5kg으로 나누어떨어지지 않을때 5kg로 나누어 떨어지게 만드는 용도로만 사용한다. 이걸 알고리즘으로 바꿔서 생각해보자 1. 우선 현재 무게가 5로 나누어 떨어지는 지 확인하고 그렇지 않으면 3kg를 챙긴다. 2. 무게가 5로 나누어 떨어지게 되었으면 그때부터는 모두 5kg을 가져가면 된다. 3. 빼는 과정에서 무게가 음수가 발생하면 -1을 출력한다. 해답 코드 #include #include int main(void){ int x=1; int count..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 count;//몇개의 답을 출력해야 하는지 count에 저장 for(int k=0;k>n>>m; for(int i=1;i

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 풀이 동적프로그래밍 문제로, 한 칸 한 칸에 들어가는 모든 값을 계산하면 너무 오랜 시간이 걸린다. 그래서 기존에 계산해 놓은 값을 바탕으로 더 빠르게 값을 찾아야 한다. 우선 각 층의 0층에는 호수만큼 산다고 했으니, 다음과 같다. 1호 2호 3호 4호 3층 2층 1층 0층 1 2 3 4 그리고 조건에 맞게 들어가야 되는 인원을 채우면 1호 2호 3호 4호 3층 1 5 15 35 2층 1 4 10 20 1층 1 3 6 10 0층 1 2..