반응형 전체 글252 [백준][Python] 15988번 1, 2, 3 더하기 3 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 코드 import sys t = int(input()) dp = [0,1,2,4] for _ in range(t): n = int(sys.stdin.readline()) for i in range(len(dp),n+1): dp.append((dp[i-3]+dp[i-2]+dp[i-1])%1000000009) print(dp[n]) 설명 처음에는 for문 안에 dp를 선언해서 새로운 n 값을 받을 때마다 dp 계산을 했더니 시간초과가 떴다. 그래서 dp를 만들어놓고 계속해서 그 값을 가져다 쓰는 방식으로 다시 코드를 .. 2022. 12. 29. [백준][Python] 9656번 돌 게임2 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 코드 n = int(input()) if n % 2 == 0: print("SK") else: print("CY") 2022. 12. 28. [백준][Python] 16194번 카드 구매하기2 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 코드 n = int(input()) p = list(map(int,input().split())) dp = [0]*(n+1) dp[1] = p[0] dp[2] = min(dp[1]*2,p[1]) for i in range(3,n+1): dp[i] = p[i-1] for j in range(1,i//2+1): dp[i] = min(dp[i],dp[j]+dp[i-j]) print(dp[-1]) 2022. 12. 27. [백준][Python] 16395번 파스칼의 삼각형 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 코드 n,k = map(int,input().split()) pascal = [[1]*i for i in range(1,31)] if n > 2: for i in range(2,n): for j in range(1,i): pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j] print(pascal[n-1][k-1]) 2022. 12. 26. [백준][Python] 11060번 점프 점프 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 코드 n = int(input()) a = list(map(int,input().split())) dp = [n+1]*n dp[0] = 0 for i in range(n): for j in range(1,a[i]+1): if i + j < n: dp[i+j] = min(dp[i+j],dp[i]+1) if dp[-1] == n+1: print(-1) else: print(dp[-1]) 2022. 12. 23. [백준][Python] 2163번 초콜릿 자르기 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿 www.acmicpc.net 코드 n,m = map(int,input().split()) print(n*m-1) 2022. 12. 22. [백준][Python] 23757번 아이들과 선물 상자 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 코드 import sys import heapq n,m = map(int,input().split()) c = list(map(int,sys.stdin.readline().split())) w = list(map(int,sys.stdin.readline().split())) hq = [] for i in c: heapq.heappush(hq,-i) for i in w: mx = -heapq.heappop(hq) if mx < i: print(0) exit() heapq.heappush(hq,-(mx-i)) print(1) 설명 .. 2022. 12. 21. [백준][Python] 1743번 음식물 피하기 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 코드 from collections import deque def bfs(x,y): global cnt queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if 1 2022. 12. 20. [백준][Python] 13699번 점화식 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 코드 n = int(input()) t = [0 for _ in range(n+1)] t[0] = 1 for i in range(1,n+1): for j in range(i): t[i] += t[j]*t[i-j-1] print(t[n]) 2022. 12. 19. 이전 1 2 3 4 5 6 7 8 ··· 28 다음 반응형
