[백준/JAVA] 1455번: 뒤집기 II

📖 문제

1455번: 뒤집기 II

 

 

 

💡  풀이 방식

• 그리디

 

(i,j) 위치에서 뒤집는 경우, 해당 칸의 왼쪽 칸과 위쪽 칸이 뒤집힌다

그러므로 오른쪽 아래 점부터 위로 올라가면서 1을 발견할 때마다 뒤집는다.

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M;
    static int[][] board;
    static int answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        board = new int[N][M];
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                board[i][j] = str.charAt(j) - '0';
            }
        }
        
        // 오른쪽 아래부터 역순으로 오면서 뒤집기
        for(int i = M-1 ; i >= 0 ; i--) {
            for(int j = N-1 ; j >= 0 ; j--) {
                // 1 만나면 axb만큼 뒤집기
                if(board[j][i] == 1) {
                    flip(j, i);
                    answer++;
                }
            }
        }
        
        System.out.println(answer);
    }
    
    private static void flip(int a, int b) {
        for(int i = 0 ; i <= a ; i++) {
            for(int j = 0 ; j <= b ; j++) {
                if(board[i][j] == 1) board[i][j] = 0;
                else                 board[i][j] = 1;
            }
        }
    }
}
 

 

---

💦 어려웠던 점

-  동전이 해당 점의 왼쪽 위를 바꾼다는 것은 알아차렸는데, 오른쪽 아래 점부터 거꾸로 찾아야 한 다는 것을 생각하지 못 했다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[ baekjoon ] 뒤집기 II 1455번 (Java )