개발자 놀이터

문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1) 번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다..

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 풀이1 P(1)부터 P(10)까지 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9로 구성되어있다. 그림에 보이는 대로 규칙을 찾아보면 마지막 숫자와 마지막에서 5번째 숫자가 더해지는 규칙이 있다. 그래서 앞에 1, 1..

이 문제는 재귀 함수를 메모이제이션(Memoization)을 추가하여 이전에 계산한 적 있는 입력 값을 저장하여 같은 연산을 반복하지 않도록 하여 시간을 단축하는 문제이다. Python에는 dictionary를 사용하여 동적 계획법을 쉽게 해결할 수 있다. dictionary는 key와 value를 짝지어 값을 저장한다. key값으로 int, string, float 등을 사용할 수 있으며 이번 문제에서 변수를 a, b, c 3개를 사용하므로 a, b, c를 tuple 안에 넣어서 키값으로 이용했다. import sys d = {} def w(a: int, b: int, c: int) -> int: if a 20: return w(20, 20, 20) elif a < b < c: if (a, b, c) ..