프로그래머스 - 카펫

완전탐색 분야라서 어떻게 풀지하다가 힌트를 조금 봤는데 찐 수학문제였다.

그림에서 아래와 같이 두 가지의 수식을 찾을 수 있다. (x는 가로길이, y는 세로길이)

위의 수식을 조합해서 가로 세로 길이를 구해야 한다.

01 첫번째 코드

위의 yellow = x * y 는 x = yellow / y로 바꿀 수 있다. 이를 이용해서 수식을 짜보면 아래와 같이 나온다.

for(int y = 1; y <= yellow; y++)
{
    int x = yellow / y;

    if (brown == (2 * x + 2 * y + 4))
    {
        answer[0] = x + 2; // 전체 가로 길이 x + 2
        answer[1] = y + 2; // 전게 세로 길이 y + 2
        break;
    }
}

아무리 봐도 올바르게 짠 것 같은데 계속 틀렸다고 결과가 나왔다. 그래서 놓친 부분이 있나 계속 읽어보다가 가로와 세로 길이가 자연수인 조건을 놓친 것을 확인하였다.

---

02 가로 세로 자연수 조건 추가한 두번째 코드

x가 자연수이기 위해서는 yellow % y의 나머지가 0이면 된다.

(즉 y가 yellow의 약수여야 한다. 그래서 완전탐색 카테고리에 있나보다)

if (yellow % y == 0)

조건 추가 코드

for(int y = 1; y <= yellow; y++)
{
    int x = yellow / y;
    if (yellow % y == 0)
    {
        if (brown == (2 * x + 2 * y + 4))
        {
            answer[0] = x + 2;
            answer[1] = y + 2;
            break;
        }
    }
}

---

코드 전문

using System;

public class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        for(int y = 1; y <= yellow;y++)
        {
            int x = yellow / y;
            if(yellow % y == 0)
            {
                if (brown == (2 * x + 2 * y + 4))
                {
                   answer[0] = x+2;
                   answer[1] = y+2;
                   break;
                }
            }
        }
        return answer;   
    }
}