백준 1166 선물 Silver III python 문제링크 1166번: 선물 첫째 줄에 N L W H가 주어진다. 모든 값은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 나의 풀이 주어지는 L, W, H에 대한 최대공약수를 찾는다는 느낌으로 접근하면 된다. 여기에 이분탐색을 곁들인. A의 최소값으로 0을 주고, 최대값으로 L, W, H에서의 최소 값을 준다. N개의 상자를 모두 넣을 수 있어야 하기 때문에 더 큰 A가 최대공약수의 조건과 N값을 충족한다면 포인터를 옮겨줘서 탐색을 계속한다. import sys N, L, W, H = map(int, sys.stdin.readline().split()) S, E = 0, max(L, W, H) for _ in rang..
백준 1915 가장 큰 정사각형 Gold V python 문제링크 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 import sys input = sys.stdin.readline N, M = map(int, input().split()) s = [[0 for i in range(M + 1)]] for i in range(n): s.append([0] + list(input().strip())) dp = [[0] * (M + 1) for i in range(N + 1)] res = 0 for i in range(N + 1): for j in range(M + 1): if ..
백준 12865 평범한 배낭 Gold V 문제링크 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 나의 코드 첫 접근은 배낭의 무게와 가치를 tuple에 저장하고, 최대 무게 안에서 존재할 수 있는 여러 물건의 가치의 합을 찾아냈다. Brute Force에 가까운 접근이었기 때문에 여러 반례들을 통과하지 못하고.. 그냥 틀려버렸다 ㅠㅠ 런타임 에러도 아니고 그냥 틀림.. 생각해보니 0-1 문제이기 때문에 당연히 DP로 푸는 것이었다. 그래서 동적..
