조준장 개발자 생존기

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 알고리즘 - 자릿수에 따른 이친수를 확인해보면 쉽게 규칙을 찾을 수 있다. - 규칙을 통해 점화식을 도출해내고 문제를 수행한다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * 91 dp[1] = 1 # 자릿수가 1일 때, 이친수의 개수 : 1 dp[2] = 1 # 자릿수가 2일 때, 이친수의 개수 : 1 # 피보나치 수 문제를 수행하듯 점화식을 구해 문제를 수행한다. # 점화식 : (n > 2)..

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 - 반복문을 통해 각 집의 색을 칠할 수 있는 최소 비용에 경우의 수를 구한다. - 이후 집에 빨간색을 칠할 경우 이전 집에 초록색과 파란색 중 비용이 작은 색을 칠한다. - 이후 집에 초록색을 칠할 경우 이전 집에 빨간색과 파란색 중 비용이 작은 색을 칠한다. - 이후 집에 파란색을 칠할 경우 이전 집에 초록색과 빨간색 중 비용이 작은 색을 칠한다. - 마지막 집까지 색칠한 후 비용의 최솟값을 출력한다. 코드 import s..

문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 알고리즘 - dp를 통해 포도주의 양을 리스트로 표현한다. - 현재 포도주를 안 먹는 경우와 연속으로 포도주를 먹는 경우와 이전 포도주를 안 먹는 경우를 비교하여 dp 리스트의 포도주의 양을 넣는다. 코드 import sys n = int(sys.stdin.readline()) m = [0] * 10001 for k in range(1, n + 1): m[k] = int(sys.stdin.readline()) dp = [0] * 10001 # 각 잔까지 먹을..

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 - 반복문을 통해 입력받은 리스트에 각 인덱스의 최댓값을 구한다. - 구하는 방법으로는 이전 수들의 합이랑 현재 인덱스의 수를 더한 값과 현재 인덱스의 수 중 큰 값을 현재 인덱스의 수에 추가하는 방식으로 수행한다. 코드 import sys n = int(sys.stdin.readline()) m = list(map(int, sys.stdin.readline().split())) dp = [m[0]] # 0번째 인덱스의 수를 미리 리스트 안에 넣는다. # 반..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 알고리즘 - 반복문을 통해 각 층의 수에 가중치를 더해준다. - 각 층의 왼쪽 줄이라면 이전 층의 왼쪽 줄에 가중치를 더한다. - 각 층의 오른쪽 줄이라면 이전 층의 오른쪽 줄에 가중치를 더한다. - 각 층의 중간 줄이라면 이전 층의 왼쪽 줄에 가중치와 오른쪽 줄의 가중치 중 큰 값을 더한다. - 반복이 끝난 후 마지막 층에 최대 가중치 값을 출력한다. 코드 import sys n = int(sys.stdin.readline()) m = [list(map(int, sys.stdin.readline().split())) for _..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 - 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다. - 길이를 구할 때 i번의 수와 그전에 수들을 비교한다. - n의 최대 값이 1000보다 작거나 같기 때문에 시간 복잡도는 O(N^2)으로 수행할 수 있다. 코드 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().spl..

문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 알고리즘 - 점화식을 통해 0과 1의 호출 횟수를 구한다. - 테스트 케이스만큰 반복하여 답을 구한다. 코드 import sys t = int(sys.stdin.readline()) dp = [1] * 42 dp[0] = 0 # 피보나치 수 0일때, 0 dp[1] = 1 # 피보나치 수 1일때, 1 # 점화식을 통해 0과 1의 호출 횟수를 구한다. for i in range(2, 41): dp[i] = dp[i - 2] + dp[i - 1] # 테스트 케이스만큼 반복하여 답을 구한다. for _ in range(t): n = int(sys.stdin.r..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 - dp를 통해 계단의 점수를 리스트로 표현한다. - 연속으로 세 개의 계단을 밟는 경우와 두 계단을 한 번에 오르는 경우를 비교하여 dp 리스트의 계단의 점수를 넣는다. 코드 import sys n = int(sys.stdin.readline()) m = [0] * 301 for k in range(n): m[k] = int(sys.stdin.readline()) dp = [0] * 301 # 계단 dp[0] = m[0] # 첫 번째 계단 dp[1] = m[..

문제 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 알고리즘 - 점화식을 통해 코드를 도출해 낸다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * (n + 1) dp[0] = 0 # 0번째 피보나치 수 : 0 dp[1] = 1 # 1번째 피보나치 수 : 1 # 반복문을 통해 n번째 피보나치 수를 구한다. for i in range(2, n + 1): dp[i] = dp[i - 2] + dp[i - 1] print(dp[n..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 알고리즘 - 점화식을 구해보면 n = 1일 때, 1이고 n = 2일 때, 2이고 n = 3일 때, 3이고 n = 4일 때, 5이고 n = 5일 때, 8인 것을 확인할 수 있다. (dp[n] = dp[n - 1] + dp[n - 2]) - n이 3보다 작거나 같을 때 직사격형을 채우는 방법의 수가 n개 이므로 n을 출력한다. - 그 외인 경우에는 점화식을 통해서 문제를 수행한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # 점화식 : n = ..