DP 5

[백준][자바] 1149 - RGB거리 - DP

📌 문제백준 | RGB거리 | SILVER 1 | DPhttps://www.acmicpc.net/problem/1149  📌 문제 탐색하기RGB 거리에는 집이 N개 존재거리는 ‘선분’1~N번 집 존재빨, 초, 파 중 하나의 색⇒ 각 비용이 존재할 때, 모든 집을 칠하는 비용의 MIN 값 구하기 규칙 :1번 집 색상 ≠ 2번 집 색상N번 집 색상 ≠ N-1번 집 색상i 번 집 색상 ≠ i-1 (2≤i≤n-1)i 번 집 색상 ≠ i+1 (2≤i≤n-1)입력 :N (집의 수)집을 빨, 초, 파로 칠하는 비용 (1~N번 순서로)출력 :모든 집을 칠하는 비용의 MIN 값   📌 알고리즘이전의 계산 결과가 이 후의 계산에 영향을 주므로, DP를 활용해서 문제를 풀어야한다.DP를 풀땐, 규칙이 가장 중요한데…이..

알고리즘/백준 2024.12.08

[백준][자바] 14430 - 자원캐기 - DP

📌 문제백준 | 자원캐기 | SILVER 2 | DPhttps://www.acmicpc.net/problem/14430  📌 문제 탐색하기제한된 범위 내에서 자원을 탐색(1,1) 부터 (N,M)까지 자원을 탐색오른쪽, 아래쪽으로 한칸 이동 가능(x,y)에 자원이 있는 경우에만 해당 자원을 채취 가능 입력 :n (세로길이 = 행), m(가로길이 = 열)n행 m열에 걸쳐 탐사영역자원 = 1, 땅 = 0출력 : 탐색할 수 있는 자원의 최대 숫자를 구하기   📌 알고리즘N과 M이 최대 300이므로, 땅의 크기는 최대 90000까지 가능만약, 완전탐색으로 접근할 경우, N,M까지 가는 경우 O(300^2) + 최대 가지의 수임DP를 통해서, 최대 광석의 개수를 계속해서 업데이트한다면?example) DP[i..

알고리즘/백준 2024.12.07

[백준][자바] 9095 - 1, 2, 3 더하기 - DP

📌 문제백준 | 1, 2, 3 더하기 | SILVER 3 | DPhttps://www.acmicpc.net/problem/9095   📌 문제 탐색하기n이 있을 때, 1,2,3의 합으로 나타내는 방법의 수를 찾기합은 1개 이상 사용해야한다.   📌 알고리즘방법이 존재하는 경우들을 모두 세야하므로, DP를 활용해야한다.DP는 그 이전의 결과값을 바탕으로 쓸 수 있으므로, 해당 값을 이용해야한다.DP[0] = 0DP[1] = 1DP[2] = 2DP[3] = 4DP[4] = 7 (=1+2+4)DP[5] = 13 (=2+4+7)DP[6] = 24 (=4+7+13)DP[7] = 44 (=7+13+24)DP[10] = 274 즉, DP[i] = DP[i-1] + DP[i-2] +DP[i-3] (i ≽ 4) ?..

알고리즘/백준 2024.12.06

[백준][JAVA] 2631 - 줄세우기 - DP, 이진탐색

📌 문제백준 | 줄세우기 | GOLD 4 | DP, 이진탐https://www.acmicpc.net/problem/2631 📌 문제 탐색하기일반적인 정렬 알고리즘은 최대 O(NlogN) ~ O(N^2) 까지 될 수 있어서… 비추하는 방법일 것 같은데문제에서 N이 고작 200이하의 정수라고 주어졌고시간제한이 1초라면, 최대 40000 즉, 1초도 안넘을 것임 ⇒ 그러므로 일반 정렬 사용해도 괜찮다.근데 문제는,,, ‘정렬’을 하는 것이 아니라, ‘최소 몇 번으로 이동 가능’이므로 ‘DP’로 풀어야할 것.3 7 5 2 6 1 4 - 3 5 63 7 4 5 2 6 1 (4번 이동) - 34563 4 5 2 6 1 7 (7번 이동) - 345671 3 4 5 2 6 7 (1번 이동) - 1 3 4 5 6 7..

알고리즘/백준 2024.11.28

[백준][JAVA] 9461 - 파도반 수열 - DP

📌 문제백준 | 파도반 수열 | SILVER 3 | DPhttps://www.acmicpc.net/problem/9461 📌 문제 탐색하기정삼각형이 나선(오른쪽 시계방향)으로 계속 돌면서 모양을 만듬  📌 알고리즘P(N)이 구현되는 모습이, 그 전의 값들로부터 영향을 받아 구현되기 때문에 이 문제는 ‘DP’ 알고리즘으로 풀 수 있다.이를 구현하기 위해, Memoization 을 활용한다.example) P(N) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9N012345678P(N)011122345       P[1] + P[5]P[2] + P[6]P[3] + P[7]즉, P(N) = P(N-5) + P(N-1) (단, N>=5)  📌 코드 설계하기TEST 입력MEMOIZATION 기법을 ..

알고리즘/백준 2024.11.26