Looan's 개발 연습장

문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 코드 n = int(input()) board = list(map(int, input().split())) top = board bottom = board for _ in range(n - 1): board = list(map(int, input().split())) top = [board[0] + max(top[0], top[1]), board[1] + max(top), board[2] + max(top..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 코드 import sys input = sys.stdin.readline n = int(input()) dp = list(list(map(int, input().split())) for _ in range(n)) for i in range(1, n): dp[i][0] += min(dp[i-1][1], dp[i-1][2]) dp[i][1] += min(dp[i-1][0],..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 n = int(input()) num = list(map(int, input().split())) dp = [1 for i in range(n)] for i in range(n): for j in range(i): if num[i] > num[j]: dp[i] = max(dp[i], dp[j]+1) print..

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 코드 n = int(input()) dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]) 설명 규칙을 찾아서 해결하는 dp 문제였다. n = 1 일 때, [1] n = 2 일 때, [10] n = 3 일 때, [100][101] n = 4 일 때, [1000][1001][..

문제 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 코드 n = int(input()) num = list(map(int, input().split())) dp1 = [1 for i in range(n)] dp2 = [1 for i in range(n)] for i in range(1, n): if num[i] = num[i-1]: dp2[i] = max(dp2[i], dp2[i-1] + 1) print(max(max(dp1), max(dp2))..

문제 https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 코드 n = int(input()) cnt = 0 while n > 0: if n % 5 == 0: cnt += n // 5 break else: n -= 2 cnt += 1 if n < 0: print(-1) else: print(cnt) 설명 단순하게 5원부터 지급하고 나머지를 2원을 지급하려고 하면 오류가 난다. 거스름돈이 5의 배수여서 딱 나누어 떨어진다면 상관이 없지만 그렇지 않다면 2를 우선 빼주어서 계산을 해야 한다. 2를 빼다가 음수로 넘어가서 n이 음수가 된다면 -1을 출력하고 그렇지 않다면 결..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 코드 n = int(input()) t = list() p = list() dp = [0] * (n+1) for _ in range(n): a, b = map(int, input().split()) t.append(a) p.append(b) for i in range(n-1, -1, -1): if t[i] + i > n: dp[i] = dp[i+1] else: dp[i] = max(p[i] + dp[i + t[i]], dp[i+1]) print(dp[0]) 설명 우선 입력값을 다 받아주고 dp 리스트를 [0]으로 n+1개 만들어..

문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 코드 n = int(input()) dp = [0] * 1000001 dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2]) % 15746 print(dp[n]) 설명 경우의 수에 대해서 생각을 해보아야 한다. 우선 길이가 1인 경우는 1이 들어가는 1가지 경우밖에 없다. 길이가 2인 경우는 00 과 11 밖에 없다. 길이가..

문제 https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 코드 n = int(input()) if n % 2 == 0: print("CY") else: print("SK") n = int(input()) dp = [''] * 1001 dp[1] = "SK" dp[2] = "CY" dp[3] = "SK" for i in range(4, n+1): if dp[i-1] == "SK": dp[i] = "CY" else: dp[i] = "SK" print(dp[n]) 설명 [풀이 1] 간단하게 생각하면 쉽게 풀리는 문제이다. n이 홀수라면 상근이가, n이 짝수라면 창영이가 게임..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 코드 n = int(input()) num = list(map(int,input().split())) dp = [-1001] * (n+1) for i in range(n): dp[i+1] = max(num[i], num[i] + dp[i]) print(max(dp)) 설명 우선 입력을 각각 받아준다. 그리고 dp를 -1001의 n+1개로 초기화 해준다. 수의 범위가 -1000