[프로그래머스] 카펫(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "카펫" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 갈색 격자와 노란색 격자의 수를 바탕으로 카펫의 가로, 세로 크기를 찾는 것이 목표입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제 링크:

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

문제 개요

Leo는 카펫 쇼핑 중 특이한 카펫을 보았습니다. 이 카펫은 중앙이 노란색으로, 테두리가 갈색으로 칠해진 격자 모양이었습니다. Leo는 카펫의 갈색 격자 수(brown)와 노란색 격자 수(yellow)는 기억했지만, 카펫의 전체 크기는 기억하지 못했습니다. 이 문제에서는 갈색 격자와 노란색 격자의 수를 바탕으로 카펫의 가로, 세로 크기를 찾는 것이 목표입니다.

문제 해결 전략

문제를 해결하기 위한 전략은 다음과 같습니다:

1. 가능한 치수 탐색: 카펫의 가로(x)와 세로(y) 길이를 순회하며 모든 가능한 치수 조합을 확인합니다.
2. 격자 수 계산: 각 치수 조합에 대해 갈색 격자 수와 노란색 격자 수를 계산합니다.
3. 조건 일치 확인: 계산된 격자 수가 주어진 갈색과 노란색 격자 수와 일치하는지 확인합니다.

코드 구현 

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    // 가능한 세로 길이 y를 3부터 탐색 시작
    for(int y = 3; y <= brown; y++){
        // 가능한 가로 길이 x를 3부터 탐색 시작
        for(int x = 3; x <= brown; x++){
            // 갈색 격자의 수 계산: 테두리 격자 수
            int sizeBrown = (x + (y - 2)) * 2;
            // 노란색 격자의 수 계산: 내부 격자 수
            int sizeYellow = (x - 2) * (y -2);
            // 조건 일치 여부 확인
            if(sizeBrown == brown && sizeYellow == yellow){
                answer.push_back(x);
                answer.push_back(y);
                return answer;
            }
        }
    }
    
    return answer;
}

코드 설명

• 이 코드는 가로와 세로 길이의 모든 조합을 탐색하여 갈색 격자와 노란색 격자의 수가 주어진 조건과 일치하는지 확인합니다.
• 갈색 격자는 테두리를 형성하기 때문에, (x + (y - 2)) * 2 공식으로 그 수를 계산합니다.
• 노란색 격자는 내부에 위치하기 때문에, (x - 2) * (y - 2) 공식으로 그 수를 계산합니다.
• 가로 길이 x와 세로 길이 y가 주어진 조건을 만족할 경우, 이 치수가 정답입니다.

결론

"카펫" 문제는 간단한 수학적 접근과 완전 탐색을 통해 해결할 수 있습니다. 주어진 갈색과 노란색 격자 수를 바탕으로 가능한 치수를 모두 탐색하여, 조건을 만족하는 치수를 찾아내는 것이 핵심입니다. 이러한 방식으로 Leo는 카펫의 정확한 크기를 알아낼 수 있습니다.