알고리즘

시간 제한 0.5 초 (추가 시간 없음) 문제 (링크) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 나의 풀이 n, k = map(int, input().split()) coins = [] for _ in range(n): coins.append(int(input())) dp = [0] * (k+1) dp[0] = 1 # dp[i] -> i원을 만들 때 가능한 경우의 수 # dp[0] -> 동전 하나를 사용하는 경우 (coin이 3일 때, d..

문제 (링크) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 나의 풀이 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) graph = [] for _ in range(n): row = list(str(input().rstrip())) graph.append(list(map(int, row..

문제 (링크) https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n, m = map(int, input().split()) current_x, current_y, d = map(int, input().split()) # d : 북 - 0, 동 - 1, 남 - 2, 서 - 3 graph = [] for _ in range(n): graph.append(list(map(..

문제 (링크) https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 나의 풀이 import sys from itertools import combinations input = sys.stdin.readline n, c = map(int, input().split()) arr = list(map(int, input().split())) # meet in the middle arr_1 = arr[:n//2] arr_2 = arr[n//2:] subsum..

문제 (링크) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 나의 풀이 import sys from collections import deque from itertools import combinations import copy input = sys.stdin.readline n, m = map(int, input().split()) graph = [] virus_locs = [] empty_locs = [] moves = [ (1, 0), (-1, 0)..

문제 (링크) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 나의 풀이 n = int(input()) ans = 0 row = [0] * n def is_promising(x): for i in range(x): if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i): return False return True def n_queens(x): global ans if x == n: ans += 1 return ..

문제 (링크) https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 나의 풀이 import sys from itertools import combinations input = sys.stdin.readline n, s = map(int, input().split()) arr = list(map(int, input().split())) # meet in the middle arr_1 = arr[:n//2] arr..

문제 (링크) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n, k = map(int, input().split()) items = [] for _ in range(n): items.append(list(map(int, input().split()))) # dp[i][j] -> 최대 무게가 j일 때..