23-07-06 TIL

문제

• 백준 17266
  • 아래 코드 처럼 가로등이 있는 좌표를 가지고 거기에서 가로등의 길이를 하나씩 + 해주어서 해결해보고자 하였다.
  • 실제로 예제 코드에서는 제대로 답을 내는 것으로 보이는데 실제 제출을 하였을 경우에는 틀렸습니다가 나옴

       while (flag == false) {

            for (int i = 0; i < lamp; i++) {

                if (position.get(i) - saveHeight >= 0 && bridgeLight[position.get(i) - saveHeight] == false)
                    bridgeLight[position.get(i) - saveHeight] = true;

                if (position.get(i) + saveHeight <= bridgeLength && bridgeLight[position.get(i) + saveHeight] == false)
                    bridgeLight[position.get(i) + saveHeight] = true;
            }

            List<Boolean> lampList = new ArrayList<>(Arrays.asList(bridgeLight));
            if (lampList.contains(false)) {
                saveHeight++;
            }
            else {
                flag = true;
            }
        }

시도

• 백준 17266
  • 문제가 무엇인지 해결하기 위해서 실제 여러가지 값을 넣어보았는데, 큰 문제는 없었다.
  • 시간초과도 아니고 그냥 틀렸습니다가 나왔기 때문에 아예 로직자체가 틀린 것인가?

해결

• 백준 17266
  • 결국 해결하지 못하고 검색을 해본 결과 이분 탐색을 사용해서 푸는 문제라고 한다.
  • 헌데 이분 탐색을 사용하지 않고 풀었을 경우에, 시간 초과가 떠야하는 것이지 아예 틀렸습니다가 나오는게 맞는가 싶다...
    -> 나중에 이분 탐색을 사용하지 않고 푸는 것도 다시 시도해보아야겠다.

오늘 푼 문제

• 백준 17266 (어두운 굴다리) - Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 굴다리 길이
        int bridgeLength = Integer.parseInt(br.readLine());

        // 가로등 갯수
        int lamp = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 램프 위치 저장
        ArrayList<Integer> position = new ArrayList<>();

        for (int i = 0; i < lamp; i++) {
            position.add(Integer.parseInt(st.nextToken()));
        }

        int res = 0;

        int min = 1;
        int max = bridgeLength;

        while (min <= max) {
            int mid = (min + max) / 2;
            boolean flag = true;

            int point = 0;
            for (int i = 0; i < position.size(); i++) {
                if (position.get(i) - mid <= point) {
                    point = position.get(i) + mid;
                }
                else flag = false;
            }

            if (bridgeLength - point > 0)   flag = false;
            else flag = true;

            if (flag) {
                res = mid;
                max = mid - 1;
            }
            else min = mid + 1;

        }

        bw.write(res + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}