[백준] 1195번. 킥다운(JAVA)

문제

https://www.acmicpc.net/problem/1195

---

풀이(20분)

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String gear1 = br.readLine();
        String gear2 = br.readLine();

        int minLength = gear1.length() + gear2.length();  // 최악의 경우: 완전 비껴서 겹치는 경우

        // gear2를 오른쪽으로 이동하면서 gear1과 겹치는 부분 확인
        for (int offset = -gear2.length(); offset <= gear1.length(); offset++) {
            if (canFit(gear1, gear2, offset)) {
                int left = Math.min(offset, 0);
                int right = Math.max(gear1.length(), offset + gear2.length());
                minLength = Math.min(minLength, right - left);
            }
        }

        System.out.println(minLength);
    }

    // gear2를 offset만큼 오른쪽으로 옮겼을 때 gear1과 겹쳐도 이와 이가 안 부딪히는지 확인
    public static boolean canFit(String gear1, String gear2, int offset) {
        for (int i = 0; i < gear2.length(); i++) {
            int gear1Idx = offset + i;
            if (gear1Idx < 0 || gear1Idx >= gear1.length()) continue;

            if (gear1.charAt(gear1Idx) == '2' && gear2.charAt(i) == '2') {
                return false;  // 이와 이가 겹침
            }
        }
        return true;
    }
}

---

문제 풀이 전략

 

말 그대로 오른쪽으로 한 칸씩 미루며 진행하는 문제이다.

-> 이 부분이 포인트로 문제에서 '킥다운'이라는 포인트를 놓치면 안 된다.

 

그 외에는 어려운 것은 없었는데 문제 풀이 초기 한 칸씩 밀고 당긴다는 이유로 비트연산을 쓰려고 했다. 최종적으로 & 연산을 해서 0이 되나! 보려고 한 것이다. 하지만 길이가 100이었기 때문에 long의 범위도 초과하여 포기했다.