[C++] 동전 (9084번)
https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제풀이 역시 dp문제.. 풀때마다 새롭고 풀때마다 머리아프다. 나만의 방법을 좀 터득했다면, 일단 이차원 배열로 만들어 생각해 보는것이다. 처음 예제를 예로 들어보자. 1, 2 원짜리 동전이 있다. 행을 동전, 열을 총 금액이라고 보고 표를 보자. 주의할점이 하나 있는데, 동전 1 2 와 2 1은 하나로 취급해야 한다. 1 2 3 4 5 6 7 8 9 1 1 1 1 2 1 2 3..
[C++] 먹을 것인가 먹힐 것인가 (7795번)
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제풀이 n과 m의 크기가 최대 20000이므로, 완전탐색을 하면 시간초과가 발생할 것이라고 생각했다. 더 좋은 방법을 생각하던중, 두 값을 정렬한 뒤 a를 순회하며 b에 이분탐색을 한 뒤 인덱스를 이용해서 더 작은 값의 개수를 구할 수 있다고 생각했다. 풀이 방법이 바로 떠올라서 풀었는데, 이분탐색에서 막혀버렸다. 맨날 공식처럼 그냥 "값이 있..