Leta Learns

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net dp 규칙 찾느라 오래 걸렸다.. 0번째 행은 j+1랑 같은 수가 된다. dp를 만들 때 인덱스를 고려해서 맨 앞에 값을 하나씩 더 넣어줬으면 편리했을텐데 귀찮아서 안 했다. 이걸 해줬으면 아마 j+1이 아니라 j랑 같은 수가 될 것이다. i == j인 경우 다리 놓는 방법이 1가지이므로 해당 조건을 추가해주었다. 그 후부터는 dp[i][j] = dp[i][j-1] + dp[i-1][j-1]..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아 디피 어렵다!!!!!!! 어떻게 풀어야 하나 감이 안 잡혔는데 시간제한이 0.5초라서 이중 for문은 절대 쓰면 안 됐고,, 혹시 DP인가... 하면서 알고리즘 분류를 확인했더니 DP가 맞았다. 처음에 for문을 0번 인덱스부터 돌려서 좀 헤맸다. 1번 인덱스부터 돌리면 바로 전 집의 최솟값과 자신의 값을 더해서 값을 갱신해주면 된다. import sys input ..