코딩 일지

문제 출처https://www.acmicpc.net/problem/1149 1149번: RGB거리첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나www.acmicpc.net실버 1 다이나믹 프로그래밍 문제이다. 규칙은 1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.다음과 같다.그럼 결국 n번 집의 색과 n-1번 집의 색이 다르기만 하면 된다는 소리다. 따라서 점화식은dp[n][0] = rgb[n]...

문제 출처https://www.acmicpc.net/problem/1005 1005번: ACM Craft첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부www.acmicpc.net골드 3 위상 정렬 문제이다.위 예시에서 4번 건물을 짓기 위해선 2번 건물과 3번 건물이 지어져있어야한다.그렇다면 2번 건물과 3번 건물이 지어졌다는 것을 어떻게 확인할 수 있을까? 바로 해당 정점으로 향하는 간선의 개수를 각각 세주면 된다.정점으로 향하는 간선의 개수를 담아주기 위한 degree 배열을 만들었다.for(int i=0,a,b;i>a>>b; graph[a].push_..

종강하기도 했고 여태 풀었던 문제들을 다시 복습하는 겸 부계정으로 문제를 다시 풀기로 마음을 먹었다. 이왕 정리하는 김에 요번에는 문제 포스팅까지 해볼려고 한다.문제 출처https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.www.acmicpc.net실버 3 다이나믹 프로그래밍 문제이다.N0 출력 횟수1 출력 횟수010101211312423535658781381321 다음과 같이 나오게 된다. 단순히 N-1번째 피보나치 수와 N번째 피보나치 수를 구하는 문제이다.그러나int fibonacci(int n) { if (n == 0) { printf("0"); ..