티스토리 뷰

백준 스터디

[BOJ 1343] 폴리오미노 C++ 풀이

박완희버서커 2025. 6. 5. 01:30
반응형

🔷 [BOJ 1343] 폴리오미노 - 실패에서 성공까지 전체 과정 기록



🔷 🧩 문제 개요


  • 문자열에는 'X'와 '.'만 있습니다.
  • 'X'는 반드시 'AAAA' (4칸), 'BB' (2칸) 블록으로 덮어야 하며, 덮지 못하면 -1을 출력해야 합니다.
  • '.'는 그대로 유지되어야 하며, 절대로 블록으로 덮으면 안 됩니다.
  • 주어진 문자열의 모든 'X'를 올바르게 덮은 결과를 출력하거나, 덮을 수 없다면 -1을 출력해야 합니다.


🔷 🚧 실패 코드 1 — 최초 시도 (내가 처음 보낸 코드)


🔷 📜 전체 코드 (실패 코드 1)


#include <iostream>

using namespace std;

int main(void)
{
	int numOfarr = 0,numTwo=0,k=0;
	char arr[51];
	cin >> arr;

	for (int i = 0; i != '\0'; i++)
		cout << arr[i];
	cout << endl;

	for (int i = 0; arr[i]!='\0'; i++)
	{
		cout << "시작 " <<numOfarr <<endl;
		if (arr[i] == '.' || arr[i] == '\0')
		{
			if (numOfarr % 2 == 1)
			{
				cout << -1 << endl;
				return 0;
			}
			else if (numOfarr % 4 == 0 && numOfarr!=0)
			{
				cout << "진입" << endl;
				while (numOfarr > 0)
				{
					for (int j = k; j < 4; j++)
						arr[j] = 'A';
					numOfarr -= 4;
				}
				 if (numOfarr % 2 == 0 && numOfarr != 0)
				{
					numOfarr -= 2;
					numTwo++;
				}
				else
				{
					for (int g = 0; g < numTwo; g++)
					{
						for (int j = k; j < 2; j++)
							arr[j] = 'B';
					}
					k = 0;
					numTwo = 0;
				}
			}
		}
		else
			numOfarr++;
	}

	for (int i = 0; i != '\0'; i++)
		cout << arr[i];
	cout << endl;

	return 0;
}

🔷 🔍 상세 분석


이 코드는 구조 자체는 좋은 시도입니다.
  • 'X'가 연속될 때마다 카운트를 올리고,
  • '.'을 만나면 이전 'X' 덩어리를 블록으로 바꾸려고 시도합니다.
  • 블록은 A(4칸), B(2칸)로 처리합니다.
하지만 이 코드에는 구조적으로 다음과 같은 심각한 문제들이 있습니다.

❌ 문제 1: 잘못된 for 루프 조건


for (int i = 0; i != '\0'; i++)
이 구문은 절대 실행되지 않습니다.
왜냐하면 i는 정수형이고, '\0'은 문자형인데 정수 0과 같기 때문입니다.
즉, i != '\0'은 i != 0으로 동작하고, i가 0일 때는 조건이 거짓이 되어 루프를 아예 돌지 않습니다.
✔️ 해결 방법:
for (int i = 0; arr[i] != '\0'; i++)
또는:
for (int i = 0; i < strlen(arr); i++)

❌ 문제 2: j < 4 같은 고정된 범위 사용


for (int j = k; j < 4; j++)
	arr[j] = 'A';
여기서 j < 4는 항상 0~3까지만 실행되기 때문에,
블록을 k 위치부터 배치하지 않고 항상 앞부분만 덮게 됩니다.
즉, X의 덩어리가 중간에 있어도 항상 배열 앞부분만 바뀝니다.
✔️ 해결 방법:
for (int j = k; j < k + 4; j++)
	arr[j] = 'A';
k는 현재 X 덩어리의 시작 위치를 나타내며, 이걸 기준으로 덮어야 정확한 위치에 배정됩니다.

❌ 문제 3: 조건이 너무 제한적임


else if (numOfarr % 4 == 0 && numOfarr!=0)
이 조건은 오직 4의 배수만 허용하기 때문에
  • X가 6개, 10개처럼 혼합되어 있어도 진입하지 못합니다.
  • 사실 6개는 AAAABB처럼 덮을 수 있는데, 이 조건은 진입 자체를 막아버립니다.
✔️ 해결 방법:
조건을 완화해서 numOfarr > 0 으로만 체크한 다음,
블록 처리할 때 4칸 A부터 최대한 덮고 남으면 2칸 B로 처리해야 합니다.

❌ 문제 4: B 블록을 실제로 쓰지 않음


numTwo++;
B 블록 개수는 카운트했지만,
실제로 B 블록을 쓰는 코드가 아래에서 정상 작동하지 않습니다.
특히 B 블록을 덮는 j 루프도 k나 위치 반영이 없어 전혀 다른 곳을 덮습니다.

❌ 문제 5: 마지막 'X' 처리 안 됨


for (int i = 0; i < strlen(arr); i++)
이 구조에서는 문자열이 'X'로 끝날 때,
마지막 'X' 덩어리를 처리할 기회를 못 얻습니다.
왜냐하면 루프가 끝나기 전에 '.'을 만나야 처리 로직이 작동하기 때문입니다.
✔️ 해결 방법:
for (int i = 0; i <= strlen(arr); i++)
문자열의 널 문자까지 순회하면 'X'로 끝나는 경우에도 정상 처리됩니다.

✅ 요약 정리표


문제 원인 설명 해결 방법
i != '\0' 루프 진입 못함 arr[i] != '\0' 또는 i < strlen()
j < 4 위치 무시하고 배열 앞만 덮음 j < k + 4
% 4 == 0만 허용 6, 10 등의 케이스 처리 못함 조건 완화: numOfarr > 0
numTwo++ B 블록을 실제로 쓰지 않음 그 자리에서 바로 쓰기
마지막 'X' 누락 '.'이 없으면 처리 안 됨 i <= strlen(arr)


🔷 🧪 실패 코드 2 — 조건 완화 시도 및 인덱스 보정


🔷 📜 전체 코드 (실패 코드 2)


#include <iostream>
#include <cstring>
using namespace std;

int main(void)
{
	int numOfarr = 0, numTwo = 0, k = 0;
	char arr[51];
	cin >> arr;

	cout << strlen(arr) << endl;
	for (int i = 0; i < strlen(arr); i++)
	{
		cout << "시작 " << numOfarr << endl;
		if (arr[i] == 'X')
			numOfarr++;
		else if (arr[i] == '.' || i == strlen(arr) - 1)
		{
			if (numOfarr % 2 == 1)
			{
				cout << -1 << endl;
				return 0;
			}
			else if (numOfarr >= 4)
			{
				cout << "진입" << endl;
				while (numOfarr > 0)
				{
					for (int j = k; j < k + 4; j++)
						arr[j] = 'A';
					k += 4;
					numOfarr -= 4;
				}
				if (numOfarr >= 2)
				{
					numOfarr -= 2;
					numTwo++;
				}
				else
				{
					for (int g = k; g < numTwo; g++)
					{
						for (int j = k; j < k + 2; j++)
							arr[j] = 'B';
					}
					k = 0;
					numTwo = 0;
				}
			}
		}
	}

	for (int i = 0; arr[i] != '\0'; i++)
		cout << arr[i];
	cout << endl;

	return 0;
}

🔷 🔍 이 코드에서 개선된 점


이전 코드에 비해 다음과 같은 진전이 있습니다:
  1. 인덱스 계산을 k + 범위로 수정
    for (int j = k; j < k + 4; j++)  // ✅ 위치 기준으로 바꿈
    → 배열 앞이 아니라 실제 k 위치부터 A 블록을 덮음
  2. 진입 조건 완화 시도
    else if (numOfarr >= 4)  // ✅ 이전보다 조건 완화
    → % 4 == 0 → >= 4로 변경하면서 좀 더 많은 상황에서 진입 가능

❌ 그러나 여전히 존재하는 문제점들


❌ 문제 1: numOfarr >= 4 조건만 처리


else if (numOfarr >= 4)
이 조건은 여전히 X가 2개일 때, 진입 못합니다.
즉, BB만 필요한 간단한 경우조차도 이 조건에서는 스킵됨.
이 때문에 X가 2개일 때 아무 작업도 하지 않아 출력에 그대로 'X'가 남음 → 오답.

❌ 문제 2: numTwo++만 하고, 실제로 B를 안 씀


if (numOfarr >= 2)
{
	numOfarr -= 2;
	numTwo++;
}
여기서 B를 써야 할 상황임에도, 단지 numTwo++만 하고 아무것도 배열에 쓰지 않음.
바로 아래에 있는 else 블록에서는 numTwo가 필요하지만, 조건 상 이쪽으로 안 들어가는 경우가 대부분이기 때문에 B는 실제로 안 쓰이게 됩니다.

❌ 문제 3: k = 0 으로 초기화 → 블록 덮는 위치 꼬임


k = 0;
  • A는 k += 4, k += 2로 증가시키고
  • B는 이 조건에서 k = 0으로 초기화
→ 이후 블록 덮는 위치가 엉망이 됨
→ 결과적으로 A와 B가 앞에서 겹쳐 써지거나, 잘못된 위치를 덮음

❌ 문제 4: 마지막 X 처리 여전히 불완전


for (int i = 0; i < strlen(arr); i++)
  • 여전히 i < strlen() 이므로, 문자열 마지막이 'X'일 경우
  • '.'을 만나지 못하고 루프가 종료됨 → 마지막 블록이 처리되지 않음

✅ 교훈 및 개선 방향


문제 설명 해결책
numOfarr >= 4만 처리 X가 2개일 때 진입 불가 조건을 numOfarr > 0으로 완화
numTwo++ 후 B 미적용 배열에 B를 실제로 쓰지 않음 B도 그 자리에서 바로 쓰도록 수정
k = 0 위치 추적 실패 B 처리 후에도 k를 누적 이동시켜야 함
마지막 'X' 처리 안 됨 널 문자 전까지밖에 안 돎 i <= strlen(arr) 사용

✅ 다음 단계


이제 위 문제들을 바탕으로 다음 코드에서는:
  • 조건을 numOfarr > 0으로 완전히 완화하고,
  • A 블록부터 최대한 덮고, 나머지 2칸은 즉시 B 블록으로 덮고,
  • k를 항상 누적 이동시키고,
  • for (i <= strlen(arr))로 끝까지 순회하며
→ 정확한 위치 계산 + 전체 블록 처리 + 끝까지 루프 실행을 구현하게 됩니다.


🔷 ✅ 최종 성공 코드 — 완전한 구조 구현


🔷 📜 전체 코드 (최종 성공 버전)


#include <iostream>
#include <cstring>
using namespace std;

int main(void)
{
	int numOfarr = 0, k = 0;
	char arr[51];
	cin >> arr;

	for (int i = 0; i <= strlen(arr); i++)  // 널 문자까지 포함
	{
		if (arr[i] == 'X')
			numOfarr++;
		else
		{
			if (numOfarr % 2 == 1)
			{
				cout << -1 << endl;
				return 0;
			}
			else if (numOfarr > 0)
			{
				while (numOfarr >= 4)
				{
					for (int j = k; j < k + 4; j++)
						arr[j] = 'A';
					k += 4;
					numOfarr -= 4;
				}
				while (numOfarr >= 2)
				{
					for (int j = k; j < k + 2; j++)
						arr[j] = 'B';
					k += 2;
					numOfarr -= 2;
				}
			}

			if (arr[i] == '.')
				k = i + 1;  // . 다음부터 X 블록 새로 시작
			numOfarr = 0;  // 덩어리 초기화
		}
	}

	cout << arr << endl;
	return 0;
}

🔷 🔍 구조 분해 및 설명


1️⃣ 입력 및 변수 초기화


char arr[51];
cin >> arr;
int numOfarr = 0, k = 0;
  • arr: 입력 받을 문자열 (최대 50글자)
  • numOfarr: 연속된 'X'의 개수를 세는 변수
  • k: 현재 블록을 덮기 시작할 인덱스

2️⃣ 메인 반복: 문자열을 한 글자씩 순회


for (int i = 0; i <= strlen(arr); i++)
  • <= strlen(arr) 를 쓴 이유는?
  • 문자열 끝이 'X'로 끝나는 경우에도 널 문자('\0')까지 도달해서 블록 처리를 할 수 있도록 하기 위함

3️⃣ 'X' 카운팅


if (arr[i] == 'X')
    numOfarr++;
  • 'X'가 나오는 동안 계속 카운트를 누적합니다.
  • 'X'가 연속된 구간 하나를 의미합니다.

4️⃣ 'X' 덩어리 처리


if (numOfarr % 2 == 1)
{
    cout << -1 << endl;
    return 0;
}
  • 'X'의 개수가 홀수라면 덮을 수 없습니다.
  • AAAA, BB는 모두 짝수 크기 블록이기 때문 → -1 출력 후 종료

5️⃣ 블록 덮기


while (numOfarr >= 4)
{
    for (int j = k; j < k + 4; j++)
        arr[j] = 'A';
    k += 4;
    numOfarr -= 4;
}
while (numOfarr >= 2)
{
    for (int j = k; j < k + 2; j++)
        arr[j] = 'B';
    k += 2;
    numOfarr -= 2;
}
  • 가능한 만큼 먼저 A 블록으로 덮습니다.
  • 4칸보다 적게 남으면 2칸짜리 B로 덮습니다.
  • 각각 덮은 후 k를 증가시켜 위치 이동합니다.
  • 모든 X를 덮은 후에는 numOfarr = 0으로 초기화합니다.

6️⃣ 구간 전환 처리


if (arr[i] == '.')
    k = i + 1;
  • '.'을 만나면, 블록을 새로 시작할 위치를 i + 1로 지정합니다.
  • '.'은 그대로 남겨두기 때문에 이 위치는 유지해야 합니다.

7️⃣ 결과 출력


cout << arr << endl;
  • 덮은 결과를 그대로 출력합니다.

🎯 이 코드가 성공한 이유


문제 해결 방법
마지막 'X' 처리 누락 i <= strlen(arr) 로 널 문자까지 포함
진입 조건 과도함 numOfarr > 0 으로 완화
블록 위치 꼬임 k로 블록 시작 위치 추적
B 블록 처리 누락 즉시 arr[j] = 'B' 로 처리
전체 흐름 엉킴 A → B 순으로 구조화, 위치 이동도 명확하게

✅ 마무리 요약


  • 이 최종 코드는 모든 X 구간을 올바르게 분석하고,
  • 덮을 수 없을 경우도 정확하게 판단하며,
  • A부터 최대한 배치 → B로 잔여 처리라는 원칙을 완벽히 구현했습니다.
반응형

'백준 스터디' 카테고리의 다른 글

BOJ 1343번 폴리오미노 python 풀이  (1) 2025.06.05
🧾 문제 설명 (BOJ 14916번: 거스름돈) 파이썬  (2) 2025.06.05
🪙 BOJ 14916번: 거스름돈 – 최소 동전 개수 구하기 C++  (1) 2025.06.02
🎬 [백준 1436] 영화감독 숌 - "666"이 들어간 n번째 수 찾기 (Python 구현)  (1) 2025.06.02
백준 1436번 영화감독 숌, C++  (0) 2025.06.01
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/09   »
일 월 화 수 목 금 토
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
글 보관함
반응형