[Greedy] 백준 25381, ABBC
이 문제의 해결 전략을 뭘까? 맨 처음 의심한 것은 A, B, C 3개중 한개로 입력이 좁혀져서 DP로 푸는 문제라고 생각했으나S의 길이가 30만에 육박한다. dp로 풀기에는 좀 크기가 큰 편이다. 그럼 어떻게? 이 문제는 Greedy 문제로, 핵심관찰이 중요한 문제다. Greedy는 규칙을 발견하면 정말 쉽게 풀 수 있지만, 규칙을 발견하지 못하면 손도 대지 못하는 양날의 검같은 문제가 많다. 그나저나 무엇이 핵심 관찰일까? 1) A, B를 지우거나 B, C를 지우거나 공통적으로 B를 포함하고 있다는 점이다. B의 갯수가 중요하다. 2) 문자열 S에서 A, B를 만들수 있는데 B, C 때문에 못만드는 경우는 어떤 경우일까? A, B에서 B를 B, C로 만드는데 사용하는 경우다. 그렇다면 A, B를 만들..
더보기
[DP 응용] BJ_1398, 동전 문제
이 문제를 Greedy하게만 풀수 있을까? 즉 큰수로 나누어 지면 계속 빼면서 숫자를 구하면 해답일까? 직관적으로 알기 어렵다면 반례를 생각해 보면 된다. 예는 31이 되겠다. 31은 Greedy하게 풀면 25, 1, 1, 1, 1, 1, 1 로 구성되어 총 6개지만, 10, 10, 10, 1로 구성하면 4개로 구성할 수 있다. 따라서 Greedy하게만은 안된다. 그렇다면 DP로만 풀수 있을까? 값의 범위가 $10^{15}$ 로 매우 크기 때문에 배열을 이용해서 단순하게 확장하는 방법으로는 해법에 다가가기 어렵다. 그럼 어떻게 해야한다? 규칙성을 발견해야 한다. 규칙성을 바탕으로 문제를 단순하게 만들 수 있어야 한다. 아래의 글이 도움이 될것 같다. 생각보다 간단하게 작성할 수 있는데, 1부터 100까지..
더보기