GaeunLee blog

백준 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 : ..