문제 (링크) 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일 때..
문제 (링크) https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 나의 풀이 이 문제는 투포인터와 이진탐색을 모두 사용할 수 있다. 1) 투포인터 사용 import sys input = sys.stdin.readline n = int(input()) liquids = list(map(int, input().split())) left_idx = 0 right_idx = n - 1 ans = abs(liquids[left_idx] + liquid..
문제 (링크) https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline target = int(input()) n = int(input()) broken = list(map(int, input().split())) # 현재 채널에서 + 혹은 -만 사용하여 이동하는 경우 min_count = abs(100 - target) for nums in range(100..
