최근 게시글
-
백준풀이
백준 1439 풀이 및 해설
개요 어떤 문제들은 입력을 짧게 치환해도 상관없는 경우가 있습니다. 이 문제가 그러한 것 중의 하나이며, 이 문제를 쉽게 풀려면 연속된 구간을 압축해야 합니다. 특정 값이 연속되는 구간은 나중에 같이 뒤집혀져야 하므로, 각 구간을 대표값 하나로 축약할 수 있겠죠. 축약 전: 1100000011 축약 후: 101 직관적으로 풀기 입력형식 되새김하기 이제 우리는 숫자가 연속되는 경우를 생각할 필요가 없습니다. from을 to로 바꿔야 한다고 했을 때, 다음과 같이 간략화된 입력만 생각하면 되는 것입니다. from으로 시작하는 경우: from from-to from-to-from from-to-from-to ... ... to로 시작하는 경우: to to-from to-from-to to-from-to-fro..
2020.12.03 16:45
-
백준풀이
백준 2437 풀이 및 해설
개요 매우 복잡해보이는 문제가 그림으로 풀면 매우 단순하게 풀리는 경우는 그리 드문일이 아닙니다. 이 문제는 수학적 귀납법으로도 풀 수 있지만, 수직선을 사용하면 훨씬 직관적이고 쉽게 풀립니다. 핵심은 측정할 수 있는 무게의 구간을 끊기지 않게 확장시키는 것 입니다. 핵심 현재 닫힌구간 [1, 10]을 측정할 수 있는 상태에서 무게가 5인 무게추가 더 주어졌다면, 기존에 측정할 수 있었던 무게 + 5를 측정할 수 있으므로, 1부터 10까지 순회하면서 5를 더한값을 추가로 측정할 수 있습니다. 즉, 닫힌구간 [1+5, 10+5]를 추가로 측정할 수 있습니다. 그렇다면 닫힌구간 [1, 5]를 측정할 수 있는 상태에서 무게가 7인 무게추가 더 주어지면 어떻게 될까요? 닫힌구간 [1, 12]를 전부 커버할 수 ..
2020.12.02 19:04
-
백준풀이
백준 2136 풀이 및 해설
개요 보자마자 팟 하고 떠오르지 않으면 매우 고생하는 문제입니다. 어느 문제나 그렇겠지만, 이러한 애드 혹 분류의 문제는 이런 경향이 더 심합니다. 핵심은 개미간 충돌을 고려하지 않는다입니다. 해설 충돌 무시하기 아래와 같이 충돌 직전의 두 개미를 생각해보겠습니다. 1초 뒤에 두 개미는 서로 충돌하여 개미의 진행방향이 다음과 같이 바뀔 것입니다. 여기서 개미가 아닌 화살표에 집중해볼까요? 화살표만 바라보았을 때, → 화살표는 ← 화살표가 있든 없든 상관없습니다. 항상 4에서 5로 이동함을 알 수 있습니다. 마찬가지로 ← 화살표도 → 화살표가 있든 없든 상관없이, 항상 5에서 4로 이동함을 확인할 수 있습니다. 위의 이유로, 각 화살표는 다른 화살표를 신경쓰지 않고 제 갈길만 가면 된다는 결론에 도달합니다..
2020.11.28 21:50
