백준 1455

1455번: 뒤집기 II (acmicpc.net)

문제 이해

해당 문제는 동전을 뒤집는 문제이다.

하지만 해당 문제에서는 동전을 하나만 뒤집는게 아니라 현재 위치 까지의 직사각형 모양의 모든 동전을 뒤집어야한다.

 

풀이

입력을 받는다.

오른쪽 아래 동전부터 처음 동전까지 이동하면서 1인동전(뒤집어진 동전)을 모두 뒤집는다.

 

여기어 오른쪽 아래 부터 뒤집는 이유는 처음 부터 시작할 경우 진행하다보면 기존에 뒤집은 동전을 다시 뒤집어야 할 수 도 있기 때문이다.

 

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

public class Main {
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int answer = 0;
        arr = new int[n][m];

        for(int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split("");
            for(int j = 0; j < m ; j++){
                arr[i][j] = Integer.parseInt(tmp[j]);
            }
        }

        //오른쪽 하단부터 역순으로 돌면서 반복
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                if(arr[j][i] == 1) {
                    reverse(j, i);
                    answer += 1;
                }

            }
        }

        System.out.println(answer);
    }


    //처음부터 해당 위치 까지 0이면 1로 1이면 0으로 뒤집기
    static void reverse(int x, int y) {
        for(int i = 0; i <= x; i++) {
            for(int j = 0; j <= y; j++) {
                if(arr[i][j] == 1){
                    arr[i][j] = 0;
                }else{
                    arr[i][j] = 1;
                }
            }
        }
    }
}