[백준/1244] 스위치 켜고 끄기 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1244
• 분류 : Simulation
• 풀이 시간 : 15분

문제 해설

1. N x N 크기의 경주로에 출발점(0, 0)에서 도착점(N - 1, N - 1)까지 경주로 설치하려 함
2. 벽(1)이 아닌 빈칸(0)에만 설치할 수 있음
3. 상하좌우 인접한 두 빈칸만 연결하여 설치할 수 있음 : 직선 도로 -> 비용 100 추가
4. 설치하려는 경주로의 방향이 바뀌는 경우 코너 생김 -> 비용 500 추가
5. 경주로를 건설하는데 최소 비용은?

Solution

풀이 접근 방법

1. 인덱스를 사용하여 배열에 접근 후 값 수정 -> ArrayList 사용(인덱스를 가진 선형 리스트)
2. 남학생 : 입력받은 수의 배수 번호를 가진 스위치 상태 반대로 전환
   1. 반복문을 통해서 배수 인덱스를 가진 스위치 접근하여 반대로 바꿈
3. 여학생 : 입력받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꿈
   1. 일단 먼저 입력받은 스위치의 상태 변환
   2. 받은 수 기준으로 양 옆으로 한칸씩 늘려가면서 양 옆의 두 값이 동일한지 확인
   3. 동일하면 상태 바꿈
   4. 동일하지 않거나, 스위치의 범위를 벗어나면 반복문 탈출
4. 스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
  static int N;
  static ArrayList<Boolean> switchList;

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

    N = Integer.valueOf(br.readLine());
    switchList = new ArrayList<Boolean>();
    StringTokenizer st = new StringTokenizer(br.readLine());

    // 인덱스와 스위치 번호를 일치시키기 위해 0번 인덱스에 미리 값 넣음
    switchList.add(0, false);

    // 스위치 상태 초기화
    for (int i = 1; i <= N; i++) {
      if (st.nextToken().equals("0"))
        switchList.add(false);
      else
        switchList.add(true);
    }

    int T = Integer.valueOf(br.readLine());
    while (T-- > 0) {
      st = new StringTokenizer(br.readLine());
      int student = Integer.valueOf(st.nextToken());
      int number = Integer.valueOf(st.nextToken());

      if (student == 1) {
        boyPlay(number);
      } else {
        girlPlay(number);
      }
    }

    StringBuilder answer = new StringBuilder();

    for (int i = 1; i <= N; i++) {
      if (switchList.get(i))
        answer.append("1 ");
      else
        answer.append("0 ");

      // 한 줄에 20개의 스위치만 출력하기 위해
      if (i % 20 == 0)
        answer.append("\n");
    }

    bw.write(answer.toString() + "\n");
    bw.flush();
    bw.close();
  }

  static void boyPlay(int number) {
    // 배열을 탐색하는 인덱스를 입력받은 숫자의 배수대로 조회
    for (int i = number; i <= N; i += number) {
      switchList.set(i, !switchList.get(i));
    }
  }

  static void girlPlay(int number) {
    int right = number + 1;
    int left = number - 1;

    // 입력받은 스위치 먼저 변환
    switchList.set(number, !switchList.get(number));

    // 양 옆을 가리키는 변수가 스위치 번위 안이고
    // 두 값이 같으면
    while (isIn(right, left) && (switchList.get(right) == switchList.get(left))) {
      // 값 변환
      switchList.set(right, !switchList.get(right));
      switchList.set(left, !switchList.get(left));

      // 입력받은 숫자 양 옆으로 늘려가면서 탐색
      right++;
      left--;
    }
  }

  static boolean isIn(int right, int left) {
    if (0 < right && right <= N && 0 < left && left <= N) {
      return true;
    }
    return false;
  }

}