조준장 개발자 생존기

문제 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 알고리즘 - 문제를 읽어보면 결국 돌을 1개를 계속해서 가져가든 3개를 계속해서 가져가든 두 개를 혼합하여 가져 가든 승자는 한 명인 것을 알 수 있다. - 상근이가 먼저 시작한 후 남은 돌의 개수가 짝수이면 창영이에 승이고 홀수이면 상근이에 승이다. 코드 import sys n = int(sys.stdin.readline()) # 상근이가 먼저 시작한 후 # 남은 돌의 개수가 짝수면 창영 승, 홀수면 상근 승 if (n - 1) % 2: print("CY") else: print("SK") github GitHub - junjange/CodingTest: 내가 푼 코딩 테스트..

문제 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 알고리즘 - 반복문을 통해 점화식을 수행한다. - A의 개수는 이전 화면에 B의 개수 - B의 개수는 이전 화면에 A의 개수와 B의 개수 index 화면 A의 개수 B의 개수 1 B 0 1 2 BA 1 1 3 BAB 1 2 4 BABBA 2 3 5 BABBABAB 3 5 6 BABBABABBABBA 5 8 7 BABBABABBABBABABBABAB 8 13 코드 import sys k = int(sys.stdin.readline()) dp = [[0 for _..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 알고리즘 - 중복 조합을 통해 문제를 수행한다. - nHr = n+r-1 C r 코드 import sys r = int(sys.stdin.readline()) # 중복 조합을 통해 문제를 수행한다. nHr = n+r-1 C r n = 10 + r - 1 a = n # n+r-1 b = r # r # aCb 구현 for i in range(1, r): a *= n - i # n x (n - i) .. x (n - r + 1)..

문제 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 ..