다이나믹프로그래밍
-
[Java] 백준 1149 RGB 거리Programming/Algorithm 2021. 3. 16. 00:11
문제 집 N개가 있다. 각각의 집은 빨강, 초록, 파랑으로 칠할 수 있다. 각각의 집에 각각의 색깔을 칠하는 가격은 다르다. 또한 인접한 집의 색깔은 같아선 안된다. 위의 규칙을 모두 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해라 풀이 N번째 집을 칠해야 하는 상황이라고 생각해보자. 1) N번째 집을 빨간색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다. - N-1번째 집이 초록색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용 - N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용 2) N번째 집을 초록색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다. - N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 ..
-
[Java] 백준 9095 1,2,3 더하기Programming/Algorithm 2021. 3. 13. 00:26
문제 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구해라. 풀이 1) 1을 1,2,3의 합으로 나타내는 방법 [1 단독으로 사용가능] - 1가지 : (1) - 1 단독 2) 2을 1,2,3의 합으로 나타내는 방법 [2 단독으로 사용가능] - 2가지 : (1,1) / (2) - [1]을 만드는 경우에 1을 합한 경우 / 2 단독 3) 3을 1,2,3의 합으로 나타내는 방법 [3 단독으로 사용가능] - 4가지 : (1,2)/ (1,1,1) (2,1) / (3) - [1]을 만드는 경우에 2를 합한 경우 / [2]를 만드는 경우에 1을 합한 경우 / 3 단독 4) 4를 1,2,3의 합으로 나타내는 방법 [단독으로 사용가능한 숫자없음] - 7가지 : (1,3) / (1,1,2) (2,..