Algorithms/DP 검색 결과

해당 글 24건

[BOJ 10844] (DP) 쉬운 계단 수 (C++)

쉬운 계단 수 (Silver 1) 문제 전체 문제 보기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근법 N자리의 계단수가 되기 위해서는 N자리에 숫자는 N-1자리의 숫자와 1만큼 차이가 나야 한다. 각 자릿수마다 끝자리 숫자를 기준으로 만들 수 있는 수의 개수를 카운트할 수 있다. 예를 들어 두 자릿수들 중 3으로 끝나는 계단 수는 23, 43 두 개가 존재하고, 5로 끝나는 계단 수는 45, 65가 존재한다. 그렇다면 세 자리 수중 4로 끝나는 계단수는 몇 개가 존재할까? 두 자리 수중 3으로 끝나는 수들의 개수와 5로 끝나는 수로 세 자릿수 중 4로 끝나는 계단 수를 만들 수 있기 때문에 총 4개를 만들 수 있다...
Algorithms/DP 2021. 8. 26. 20:43

[BOJ 1932] (DP) 정수 삼각형 (C++)

정수 삼각형 (Silver 1) 문제 전체 문제 보기 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 접근법 삼각형에서 임의의 위치 (i, j) (i: 열, j: 행)의 수를 a(i, j)라 하고, 삼각형의 꼭짓점에서 출발해서 임의의 위치 (i,j)까지 도달했을 때 경로의 최대합을 f(i, j)라고 했을 때 f(i, j)는 임의의 위치 (i,j)의 좌측 상단 (i-1, j-1)까지의 경로의 최대합과 우측 상단(i-1, j)까지 경로의 최대합에 (i, j)의 수 a(i, j) 값을 더한 값이다. 점화식으로 표현하면 다음과 같다. \[f(i, j) = \mbox{max}(f(i-1, ..
Algorithms/DP 2021. 8. 25. 09:30

[BOJ 1149] (DP) RGB 거리 (C++)

RGB 거리 (Silver 1) 문제 전체 문제 보기 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 접근법 이 문제에서 구해야 하는 값은 총 N개의 집들이 각각 R, G, B 색상으로 칠하는데 필요한 비용이 주어질 때 모든 집을 칠하기 위한 최소의 비용을 구해야 한다. 집을 칠하기 위한 규칙은 옆집과 다른 색이기만 하면 된다. 아래와 같이 같은 색이 연속해서 나오지 않은 경우 모두 가능하다. RGRBRGRBRGRBRBRG RGBRGBRGRBGBRBGR 즉 N번 째 집을 칠할 수 있는 모..
Algorithms/DP 2021. 8. 24. 09:31

[BOJ 9461] 파도반 수열(C++)

파도반 수열(Silver 3) 문제 전체 문제 보기 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근법 파도반 수열은 다음과 같다. 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 파도반 수열의 규칙을 쉽게 찾을 수 있다. 임의의 위치 \(n\)에서 수열의 값을 \(f(n)\) 이라고 했을 때 \(f(n)\) 은 \(f(n-2)\) 와 \(f(n-3)\)의 합으로 이루어져 있다. 문제에서 주어진 삼각형 그림을 보면 \(f(n)\)은 \(f(n-1)\)과 \(f(n-5)\)번로 표현되어 있는데..
Algorithms/DP 2021. 8. 17. 09:57