[백준 1195] 킥다운 - JAVA

BOJ Link

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

 

 

 

 

풀이 과정

아이디어를 떠올리긴 쉽고, 구현은 실수하기 쉬운 문제였다.

 

1or2의 이진 값이기에 비트마스킹을 적용할 수 있고,

각 기어의 길이는 100이하이므로,

first 기어의 왼쪽/오른쪽에 값이 0인 100길이의 인덱스를 pad로 놓은 first[100 + first.len + 100]배열을 구성하여

인덱스 처리를 쉽게 할 수 있다.

 

후자의 방법이 생각은 났지만 사용하지 않았다. 쉽다고 착각하여 무작정 코드를 작성하고 테스트케이스를 넣으면서 쓴맛을 봤다. 

 

second 기어가 first 기어의 왼쪽에 있을 때, 겹칠때, 오른쪽에 있을 때 3개의 케이스를 나누어 완전탐색했다.

이 때, 기어가 겹치는 2번째의 경우는 second가 first보다 길이가 클 수 있음에 유의해야한다.

 

2번째 경우에 해당하면 값은 first의 길이와 second의 길이 중 더 큰 값 이며, 무조건 최적해가 되기 때문에

한 번이라도 이 경우에 해당한다면 추가 탐색 없이 종료해도 된다.

 

 

유의할 점

맞물리다의 정의가 모호하다.

https://www.acmicpc.net/board/view/100800

 

1.

문제에서 맞물리지 않는 경우는 명시되어있지 않다. 따라서 문제 자체에 오류가 없다면 맞물리지 않은 경우는 없다.

기어간의 겹치는 부분이 없을 때도 맞물린 것으로 처리하며, 이때 답은 두 기어 길이의 합이 된다.

// input

22

22

// ans

4

// wrong ans

Integer.MAX_VALUE, 0, -1 ...

 

2. 

홈(1)과 홈이 접하는 것도 맞물리는 것으로 간주한다. 즉, 이(2)와 이가 맞물리지만 않으면 된다.

// input

11

11

// ans

2

// wrong ans

4

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] first = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        int[] second = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        int fl = first.length;
        int sl = second.length;
        int ans = fl + sl;

        // case 1 - second가 first의 왼쪽일 때

        // second의 탐색 시작 인덱스
        int start = sl - 1;
        // 겹치는 부분
        int comp = 1;
        while (comp < sl && comp < fl) {
            boolean isAns = true;

            for (int i = 0; i < comp; i++) {
                if (first[i] + second[start + i] > 3) {
                    isAns = false;
                    break;
                }
            }

            if (isAns) ans = Math.min(ans, fl + sl - comp);
            start--;
            comp++;
        }

        // case 2 - second가 first와 완전히 겹칠 때
        int len = Math.max(fl, sl);

        if (fl > sl) {
            for (int i = 0; i + sl <= fl; i++) {
                boolean isAns = true;

                for (int j = 0; j < sl; j++) {
                    if (first[i + j] + second[j] > 3) {
                        isAns = false;
                        break;
                    }
                }
                if (isAns) {
                    ans = Math.min(ans, len);
                    // 사실상 해당하면 정답임
//                    System.out.println(ans);
//                    return;
                }
            }
        } else {
            for (int i = 0; i + fl <= sl; i++) {
                boolean isAns = true;

                for (int j = 0; j < fl; j++) {
                    if (second[i + j] + first[j] > 3) {
                        isAns = false;
                        break;
                    }
                }
                if (isAns) {
                    ans = Math.min(ans, len);
                    // 사실상 해당하면 정답임
//                    System.out.println(ans);
//                    return;
                }
            }
        }

        // case 3 - second가 first의 오른쪽일 때
        comp = 1;
        while (comp < sl && comp < fl) {
            boolean isAns = true;

            for (int i = 0; i < comp; i++) {
                if (first[fl - comp + i] + second[i] > 3) {
                    isAns = false;
                    break;
                }
            }

            if (isAns) ans = Math.min(ans, fl + sl - comp);
            comp++;
        }

        System.out.println(ans);
    }
}