전체 글

[Baekjoon] 2579번 : 계단 오르기

실버 3 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 계단이 3개 보다 작으면 모든 계단을 밟는 것이 무조건 최대이다. 하지만 3개 이상일 경우엔 연속으로 세 개의 계단을 밟을 수 없기 때문에 두 가지 경우로 나누어 생각을 해볼 수 있다. 1) 한 칸 이전(n-1)에서 n번째 칸으로 온 경우 연속 두 개의 계단을 밟은 셈이므로 n-2칸은 밟을 수 없다. 따라서 n-3까지의 최대 점수에 한 칸 이전 계단의 비용과 현재 계단의 점수를 더한다. 2) 두 칸 이전(n-2)에서 n번째 칸으로 온 경우 연속이 되지 않..

[Baekjoon] 1149번 : RGB거리

실버 1 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 집을 색칠하는 가지수는 세가지 이다. 1 2 3 4 5 6 위와 같은 형태로 집을 색칠하는 비용이 주어진다. 첫 번째 집만 칠한다면 최소값인 1을 선택하면 되지만 두집 이상인 경우 앞집과 색이 겹쳐선 안된다. 만약 두 번째 집을 빨간색으로 칠한다면 첫 번째 집은 파란색 또는 초록색으로 칠해져 있어야 한다. 첫 번째 집을 파란색과 초록색으로 칠하는 비용 중 더 작은 값과 더해준다. house[1][0] = min(house..

[Baekjoon] 9461번 : 파도반 수열

실버 3 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 풀이 파도반 수열의 규칙을 찾아보면 다음과 같다. n = 1 -> 1 n = 2 -> 1 n = 3 -> 1 n = 4 -> 2 n = 5 -> 2 n = 6 -> 3 (f(1)+f(5)) n = 7 -> 4 (f(2)+f(6)) n = 8 -> 5 (f(3)+f(7)) n = 9 -> 7 (f(4)+f(8)) n = 10 -> 9 (f(5)+f(9)) 5까지는 규칙이 없지만 6부터 규칙이 나타난다. 즉 n이 5보다 클때 다음 점화식을 만족한다. dp[..

[Baekjoon] 1904번 : 01타일

실버 3 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 풀이 남은 타일은 1하나로만 이루어진 타일, 0 두개로 이루어진 타일 한쌍이다. n부터 써보면서 규칙을 찾아보면 다음과 같다. 즉, 피보나치 수열과 같은 형태로 진행됨을 알 수 있다. n = 0, 1개 n = 1, 1개 n = 2, 00, 11 -> 2개 (1+1) n = 3, 100, 001, 111 -> 3개 (1+2) n = 4, 0011, 1100, 0000, 1001, 1001 -> 5개 (2+3) n = 5, 00111, 10011, 1100..