[알고리즘 PS] 백준 15729번 방탈출 자바 문제풀이

문제

해당 포스팅은 백준의 백준 15729 방탈출 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

15729번: 방탈출

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 Greedy 알고리즘으로 해결할 수 있다.

 

우선 2가지의 불을 나눠서 생각할 수 있는데

 

1. 불이 모두 꺼진 상태 -> starts
2. 원하는 불이 켜진 완성 상태 -> ends

 

문제 해결 컨셉은 starts 에서 배열 원소 하나씩 돌며 ends 배열과 다른 인덱스가 있다면 뒤의 2개 불을 toggle 시켜준다는 것이다.

 

ends 배열의 길이만큼 반복을 돌며 계속해서 toggle 시켜주고 toggle 횟수만큼 counting 을 해주면 된다.

 

하지만 주의해야 하는 것이 2개 이후의 불을 toggle 할 때, 배열 인덱스의 size 보다 넘어가는 상황이 발생할 수 있는데, 이 때는 아무 연산을 하지 않고 넘어가면 된다.

정답 코드

public class Main {

    private static int answer = 0;

    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 n = Integer.parseInt(br.readLine());

        String[] rooms = br.readLine().split(" ");
        String[] start = new String[n];
        for (int i = 0; i < rooms.length; i++) {
                start[i] = "0";
        }

        for (int i = 0; i < rooms.length; i++) {
            if (rooms[i].equals(start[i])) continue;
            toggleThree(start, i);
        }
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
    private static void toggleThree(String[] a1, int index) {
        for(int i = 0; i < 3; i++) {
            if(i + index < a1.length) {
                toggle(a1, i + index);
            }
        }
        answer++;
    }

    private static void toggle(String[] a1, int index) {
        if(a1[index].equals("0")) a1[index] = "1";
        else a1[index] = "0";
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.