Koala - 14기/코딩테스트 준비 스터디

[백준/c++] 1455번: 뒤집기 ||

소코기 2024. 4. 8. 00:38

https://www.acmicpc.net/problem/1455

 

1455번: 뒤집기 II

세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고

www.acmicpc.net

  • 코드
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include<cmath>
#include<stack>
#include<deque>

#define LL long long
using namespace std;
int arr[101][101];

void reverse(int a, int b) {
	for (int i = 1; i < a + 1; i++) {
		for (int j = 1; j < b + 1; j++) {
			if (arr[i][j] == 1) {
				
				arr[i][j] = 0;
				continue;
			}
			else arr[i][j] = 1;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	int m;
	string s;
	cin >> n >> m;
	for (int i = 1; i < n + 1; i++) {
		cin >> s;
		for (int j = 1; j < m + 1; j++) {
			arr[i][j] = s[j - 1] - '0';
		}
	}
	int cnt = 0;
	for (int i = n; i > 0; i--) {
		for (int j = m; j > 0; j--) {
			if (arr[i][j] == 1) {
				reverse(i, j);
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}
  • 알고리즘 분류 : 그리디 알고리즘
  • 문제 해설

동전을 뒤집은 순서가 오른쪽에서 왼쪽으로 아래에서 위로 해도 된다는 것만 알면 구현하기 쉬운 문제였다. 이전 뒤집은 것에 영향을 안주고 0으로 갱신해 나가며 카운트를 해주면 된다. 예외처리할 것도 없다.