백준 1343번 __폴리오미노__(C++)

문제

1343번: 폴리오미노

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

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

정답 코드

#include <iostream>
#include <string>
using namespace std;
string input;
int main(){
	cin >> input;
	int s_size = input.size();
	for(int i=0;i < s_size;i++){
		int cnt=0;
		for(int j=0;j+i<s_size;j++){
			if (input[i+j] =='X')
				cnt++;
			else
				break;
		}
		if (cnt%2 ==1){
				cout << -1 << "\n";
				return 0 ;
		}
		while (cnt!=0){
			if (cnt % 4 == 0){
				for(int j=0;j<4;j++){
					input[i+j] = 'A';
				}
				cnt-=4;
			}else if (cnt % 2 ==0){
				for(int j=0;j<2;j++){
					input[i+j] = 'B';
				}
				cnt-=2;
			}
		}
	}
	cout << input << "\n";
}

문제 풀이의 흐름

• 제한시간이 2초인데, 보드판의 크기가 최대 50개여서 최적화해서 코드를 짜지 않아도 된다고 생각했다.

• 입력을 처음부터 끝까지 탐색을 한다.

• 탐색 도중 X의 갯수를 세주고 X가 아니면 숫자세기를 멈추고 나온다.

• X의 갯수가 홀수라면 무조건 만들 수 없다.

• A를 먼저 넣는 것이 더 좋은 방법이므로, 4개 이상이면 A로 다 채우고, 2만 남았을 때 B를 채운다.

• 그것을 계속해서 반복해준다.

주의 할 점

딱히 없다. 괜히 최적화의 함정에 빠지지 말도록 하자.

더 효율적으로 짤 수 있지만, 모의 코테에서 풀었던 풀이이기 때문에 효율보단 통과를 우선적으로 생각했따.

반성 및 고찰

쉬운 문제여서 비효율적으로 짰다.

그것이 코테에서는 더 유리한 방법인 것 같다. 시간 복잡도를 먼저 계산해보고 여유있다고 생각되면 바로 그 로직으로 실행하는 것이 중요한 포인트 인 것 같다.

Uploaded by N2T