본문 바로가기

정올

[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] 백준 28218 격자 게임 어떤 알고리즘으로 문제를 풀어야 할까? 문제의 크기는 300 * 300에, 말의 위치가 다시 원위치로 돌아가는 방법이 없다. 문제를 하위 문제로 나누어 풀어도 문제가 없다는 이야기. 즉, dynamic programming이 가능한 문제라는 뜻이다. 점화식을 어떻게 수립해야 할까? $$ dp[x][y][turn] $$ (x, y)의 위치에서 현재 turn(한국 or 정올)의 차례일 때 이기는 사람의 번호로 점화식을 정의할 수 있다. 그렇다면, 최선을 다한다는 것은 어떻게 표현할까? 현재 첫번째 한국이가 이길 때를 0으로 표시하고, 두번째 정올이가 이길 때를 1로 설정한다. 그리고, 첫번째 한국이의 turn일 때는 정올이가 이긴다고(=1) 초기값을 설정하고 가능한 케이스에서 최소값(=0, 한국이가 이기는 .. 더보기

티스토리툴바