GaeunLee blog

무게 제한이 걸려있는 가방에 가치를 최대로 하게끔 물건을 넣는 방법을 알아보자! 대표 문제: 12865 평범한 배낭 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 가치를 최대로 하는 문제이니, dp에 가치를 저장해서 해결한다. Value(i,w)란 i번째 물건까지, w무게만큼 골랐을 때 최대가치를 말한다고 가정한다. (단, i는 물건의 index, w는 현재 가방에 담겨있는 무..

백준 17626 www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 1. 주어진 수와 같거나 작은 가장 큰 제곱수를 우선으로 그리디하게 풀면 틀린다. 더 작은 경우가 존재 ex) 11339 = 106^2 + 10^2 + 1^2 + 1^2 + 1^2 (5 : 오답) 11339 = 105^2 + 17^2 + 5^2 (3 : 정답) 2. dp를 이용해 min을 갱신하면서 찾는다. dp[n] = 합이 n이 되는 제곱수의 개수라고 하자..

백준 20047 www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 손가락으로 짚은 두 동전을 편의상 Fcoin이라고 하자. 1. 문자열 S(Fcoin을 제외), T의 인덱스를 증가시키면서 비교하고, 달라지는 경우에 T와 Fcoin을 비교했다. 그럴 경우 반례가 생긴다. -> 문자열 S(Fcoin을 제외)에서 비교할 문자와 와 Fcoin이 같은 경우 어떤 경우로 체크해줘야 하는지 고려하지 않았다. 3 xxo xox 0 2 ans : ..