조준장 개발자 생존기

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 알고리즘 - 반복문을 통해 각 스티커 인덱스의 최댓값을 구한다. - 카드의 크기가 2일 때인 즉, 인덱스가 1일 때 최댓값은 이전 대각선의 스티커 점수의 합이다. - 인덱스가 1보다 클 경우에는 두칸 전에 스티커 값과 이전 스티커 값 중에서 큰 값과 현재 스티커의 값을 더한 값이 최댓값이 된다. - 표를 통해 확인하면 더 쉽게 이해할 수 있다. 예제 입력 1) index 0 1 2 3 4 0 50 10 + 30 = 40 max(100, 30) +..

문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 알고리즘 - dp를 통해 타일이 n개일 때의 규칙을 찾아 점화식을 도출해 낸다. - 점화식 : f(n) = f(n - 1) + f(n - 2) - 반복문을 통해 점화식을 표현한다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * 1000001 dp[1] = 1 # 1 dp[2] = 2 # 00, 11 dp[3] = 3 # 100, 001, 111, # dp[4] = 5 # 0011, 1100, 1001, 0000..

문제 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 알고리즘 - 반복문을 통해 각 카드 개수의 지불하는 최대 금액을 구한다. - 각 카드의 개수의 지불하는 최대 금액과 이전의 카드를 지불한 최대 금액 + 현재 카드팩 가격을 비교한다. 예를 들어, 예제 입력 1을 예시로 두어 코드를 수행하면 다음과 같다. dp[1] = p[1] dp[2] = dp[1] + p[1] or dp[0] + p[2] dp[3] = dp[2] + p[1] or dp[1] + p[2] or dp[0] + p[3] dp[4] = dp[3] + p..

문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 알고리즘 - 반복문을 통해 각 다리를 연결한다. - mCn 을 구현하여 문제를 수행한다. 코드 import sys t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복 for _ in range(t): n, m = map(int, sys.stdin.readline().split()) a = m b = n # mCn 구현 for i in range(1, n): a *= m - i # m! b *= n - i # n! print(a ..

문제 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 알고리즘 - 반복문을 통해 퇴사하기 전날부터 현재까지 확인한다. - 상담 기간이 퇴사 이후 까지라면 현재 상담 비용은 이후의 비용이 된다. - 퇴사 이전에 상담이라면 현재 상담 비용 + 현재 상담을 끝낸 후 비용과 상담을 받지 않는 비용일 비교하여 더 큰 값을 현재 비용이 된다. 코드 import sys n = int(sys.stdin.readline()) m = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] dp = [0] * (n + 1) # 반복문을 통해 퇴사하기 전날부터 현재까지 확인 for i in range(n - ..

문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 알고리즘 - 점화식을 구한다. - 반복문을 통해 구한 점화식을 코드로 수행한다. 코드 import sys t = int(sys.stdin.readline()) # 테스트 케이스만큼 반복한다. for _ in range(t): n = int(sys.stdin.readline()) dp = [1] * (n + 1) # 반복문을 통해 점화식을 코드로 수행 # n = 1일때 1, n = 2일때 1, n = 3일때 1, n = 4일때 2, n = 5일때 2, n = 6일..

문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 알고리즘 - 점화식을 구해보면 n = 1일 때, 1이고 n = 2일 때, 3이고 n = 3일 때, 5이고 n = 4일 때, 11인 것을 확인할 수 있다. - 점화식 : dp[n] = dp[n - 1] + (dp[n - 2] * 2) 코드 import sys n = int(sys.stdin.readline()) dp = [0] * 1001 dp[1] = 1 dp[2] = 3 # 반복문을 통해 점화식을 코드로 수행 # n = 1일때 1가지, n = 2일때 3가지, n = 3일때 5가지, n ..

문제 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 # 각 잔까지 먹을..