목록baekjoon (solved.ac) (50)
Hikenny25
https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net - 메모이제이션 (구현) import sys input = sys.stdin.readline n, m = map(int, input().split()) nl = [0] + list(map(int, input().split())) sl = [0] * (n+1) for i in range(1, n+1): sl[i] = sl[i-1] + nl[i] for _ in range(m)..
https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+2) dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = dp[i-1] + 2 * dp[i-2] print(dp[n] % 10007) 타일링 문제 1에서 언급했던 경우의 수에, n-2 길이의 상자에 (가로 2, 세로 2) 정사..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+2) dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n] % 10007) 길이가 n인 상자를 채우는 방법은 길이가 n-1인 상자에 (세로 2, 가로 1) 블럭 하나..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - DFS - BFS import sys input = sys.stdin.readline from collections import deque class Graph: def __init__(self, size): self.size = size self.matrix = [[0] * size for _ in range(size)] self.visited = [0]..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net - 그래프 탐색 (BFS 사용) import sys input = sys.stdin.readline from collections import deque class Graph: def __init__(self, size): self.size = size self.matrix = [[0] * size for _ in range(size)] self.visited = [0] * size def addEdg..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net - 재귀 (메모이제이션) import sys input = sys.stdin.readline def step(x): if x
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+4) dp[2] = dp[3] = 1 for i in range(4, n+1): if i % 3 == 0 and i % 2 == 0: dp[i] = min(dp[i-1], dp[i//2], dp[i//3]) + 1 elif i % 3 == 0: dp[i] = min(dp[i-1], dp[i//3]) + 1 elif i % 2 == 0: dp[i] = ..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net - 구현 import sys input = sys.stdin.readline n, m = map(int, input().split()) d = dict() for _ in range(n): ip = input().split() d[ip[0]] = ip[1] for _ in range(m): ip = input()[:-1] print(d[ip]) dict를 안다면 브론..
https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline n = int(input()) p = list(map(int, input().split())) p.sort() dp = [0] * (n+1) dp[0] = 0 dp[1] = p[0] for i in range(2,n+1): dp[i] = dp[i-1] + sum(p[:i]) print(dp[n]) 보니까 디피로 안풀어도 ..
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net - Greedy import sys input = sys.stdin.readline n,k = map(int, input().split()) a = list() for _ in range(n): a.append(int(input())) cnt = 0 while n >= 0: coin = a[n-1] cnt += (k // coin) ..