본문 바로가기

ps java4

[ps java] BOJ 1149 RGB 거리 해설 DP를 학습할 수 있는 좋은 문제다! [실버1]https://www.acmicpc.net/problem/1149  문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초.. 2025. 1. 31.
[ps java] BOJ 1912 연속합 해설 (카데인 알고리즘) DP를 학습하기 좋은 웰-노운 문제이다 [실버2] https://www.acmicpc.net/problem/1912 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 11010 -4 3 1 5.. 2025. 1. 31.
[ps java] 재귀 -> DP 변환 예시 코드(BOJ 9184) https://www.acmicpc.net/problem/9184재귀를 DP로 바꾸는 문제이다 [실버2]재귀 호출만 생각하면 신이 난다! 아닌가요?  아래와 같은 재귀 호출 알고리즘 코드가 있다하지만 a b c 에 15 15 15 만 입력하더라도 실행하는 데에 너무 많은 시간이 걸린다따라서 우리는 아래의 코드를 DP로 변형해 볼 것이다import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); whi.. 2025. 1. 19.
[ps java] 피보나치 수열 알고리즘(재귀, DP) 우리가 일반적으로 알고 있는 피보나치 수열에 대한 재귀 알고리즘은 다음과 같다import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); System.out.println(fibonacci(n)); br.close(); } private static int fibonacci(int n) { if (n == 0) {.. 2025. 1. 19.

티스토리툴바