성장하는 개발자의 블로그

https://www.acmicpc.net/problem/12865 DP에 유형에 약한 편이라 처음 이 문제를 풀 때 점화식 구성에 있어서 시간이 좀 오래 지체되었다. 처음에는 배낭이 견딜 수 있는 무게의 시작을 0부터 시작하고 하였는데 잘 풀리지 않았었고, 고민을 하다가 역순으로 최대 무게에서 감소하는 점화식을 적용하니 풀린 문제이다. 아래는 정답에 해당하는 코드이다.  public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int[] dp = new int[K + 1]; // dp[w..

https://www.acmicpc.net/problem/2449  문제최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 있다. 이 전구 N개를 다음의 그림과 같이 한 줄로 배치하여 서로 연결한다. (동그라미 안의 숫자는 전구의 색을 의미한다) 각 전구는 스위치가 있어서 전구의 색을 임의의 색으로 바꿀 수 있다. 하나의 전구 색을 바꾸는 경우에는, 색이 바뀌는 전구에 인접한 전구가 같은 색이면, 이 전구의 색도 같이 바뀌게 되며 인접한 전구가 다른 색이 나올 때까지 계속 바뀌게 된다. 예를 들어, 위의 그림에서 4번 전구의 색을 2번 색으로 바꾸면, 5번 전구가 4번 전구와 같은 색이었으므로 2번 색으로 바뀌고, 6번 전구도 5번 전구와 같은 색이었으므로 2번 색으로 바뀌게 된다. 즉, 4번 전구의..