[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를 만들..
더보기
