본문 바로가기

Problem Solving1216

[백준] 9465 스티커 - Dynamic Programming / Java • 문제 링크 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net • 풀이 과정 2차원 dp배열을 생성하고, 문제에 주어진 행과 열의 정보에 따라 dp[2][n + 1] 의 크기로 생성한다. 문제에 주어진 조건에 의해 특정 스티커를 선택할 경우 해당 스티커의 상하좌우는 선택할 수 없으며, 탐색을 왼쪽에서 오른쪽으로 수행할 것이기 때문에 선택한 스티커의 오른쪽 또한 선택할 수 없게 되는 것에 초점을 둔다. 특정 스티커를 선택하기 위해서는 해당 스티커의 왼쪽 대각선 방향의 첫번째, 또는 두번째 중 하나만을.. 2022. 8. 31.
[백준] 11057 오르막 수 - Dynamic Programming / Java • 문제 링크 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net • 풀이 과정 2차원 dp배열을 생성, 이는 dp[자릿수][0 ~ 9] 를 나타낸다. 먼저 i = 0 ~ 9, dp[0][i] = 1 로 초기화한다. 그리고 규칙성을 찾기 위하여 1 ~ 3 의 자릿수의 값의 따라 오르막 수의 개수를 나타내면 아래와 같다. n / j 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 1 1 10 9 8 7 6 5 4 3 2 1 2 55 45 36 28 21 15.. 2022. 8. 30.
[백준] 1309 동물원 - Dynamic Programming / Java • 문제 링크 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net • 풀이 과정 n칸 마다 두 개의 방이 존재하고, 사자들을 배치할 때 가로 또는 세로로 붙어서 배치할 수 없는 조건에 의하여 이전 칸에 사자를 배치하지 않는 경우을 제외하고 이전에 배치된 방에 따라 현재 방의 배치가 결정된다. 배치하는 경우의 수는 3가지로, dp[n][0] 은 두 개의 방 모두 배치하지 않은 경우, dp[n][1] 은 첫 번째 방에 배치한 경우, dp[n][2] 은 두 번째 방에 배치한 경우를 나타낸다. 따라서 2차원 dp배열을 dp[n + 1][3] 의 크기로 생성하고, dp[1][0] = dp[1][1] = dp[1][2] = 1 로 각각의 경우를 초기화한다... 2022. 8. 29.
[백준] 1149 RGB거리 - Dynamic Programming / Java • 문제 링크 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 생성하고, 이는 dp[집][색상] 을 의미한다. 이후 각각의 집에 색을 칠하는 비용을 입력받으며, 무조건 첫번째 집에 가장 적은 비용의 색을 칠함에 따라 정답을 구할 수 있는 것이 아니기 때문에 첫번째 집에 3가지 색을 칠한 경우의 수를 모두 구한다. 현재 집까지 색을 칠하는 최소 비용은, 이전 집에서 현재 집과 다른 두 색상 중 적은 비용과 칠할 색의 비용을 합한 값이므로 i번째 집에.. 2022. 8. 28.
[백준] 2225 합분해 - Dynamic Programming / Java • 문제 링크 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 생성하고, dp[n + 1][k + 1] 으로 크기를 지정한다. 이때 n = 1 일 때 i 개로 n을 만드려면 각각 i 개의 경우의 수가 존재,(dp[1][i] = i) i 를 k = 1 개로 만드려면 각각 1개의 경우의 수가 존재하므로 해당 값들을 초기화시킨다.(dp[i][1] = 1) 이어서 규칙성을 찾기 위해 n = 1 ~ 3, k = 1 ~ 3 범위의 예시는 아래와 같다. dp[1][1] : 1 (1) dp[1][2] : 2 (1 + 0, 0 + 1) dp[1][3] : 3 (1 + 0 + 0, 0 + 1 + 0, 0 + 0 .. 2022. 8. 27.
[백준] 1699 제곱수의 합 - Dynamic Programming / Java • 문제 링크 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net • 풀이 과정 각각의 자연수 n 의 최대 제곱수의 갯수는 n 이므로, 반복문을 통해 제곱수의 최대 개수를 초기화한다.(dp[i] = i) 1 ~ 3 은 제곱수의 최솟값 또한 1 ~ 3 이며, 나머지는 아래와 같이 구할 수 있다. n 제곱수 점화식 개수 dp[4] 2^2 dp[4 - 2^2] + 1 = dp[0] + 1 1 dp[5] 2^2 + 1^2 dp[5 - 2^2] + 1 = dp[1] + 1 2 dp[.. 2022. 8. 26.

티스토리툴바