[Java] 완전탐색 - 카펫 (Lv2)

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

프로그래머스

 

✔ 입출력 예시

카펫 - 입출력 예시

 

 

❓ 풀이과정

     1️⃣ 예제에 나와있는 설명을 토대로 본다면 테두리 1줄만 갈색으로 칠해져 있다는 것을 알 수 있음

     2️⃣ 먼저 다음과 같이 3부분으로 나누어 생각해보았다

           노란색 칸의 가로 : yw / 노란색 칸의 세로 : yh

           갈색 칸의 가로 : bw / 갈색 칸의 세로 (가로 칸에 포함된 위아래 2칸 제외) : bh

     3️⃣ 그림에 의하면 하나의 bw는 yw길이의 2만큼 크며, bh는 yh의 길이와 같음

     4️⃣ 식을 세워보면 아래와 같음

           갈색 칸의 수 = yh * 2 + (yw + 2) * 2

           전체 넓이  = 노란색 칸의 수 + 갈색 칸의 수 = (yh * yw) + (bw * 2 + bh * 2)

                                                                                = (yh * yw) + (yh * 2 + (yw + 2) * 2)

     5️⃣ 위의 식을 생각해보며 먼저 노란색 칸이 만들 수 있는 직사각형의 모양 즉, 가로와 세로 모두 구하기

     6️⃣ 구한 경우의 수를 모두 탐색하며 `yh * 2 + (yw + 2) * 2`의 결과가 brown과 같을 때 반복문을 멈추고

           정답 배열 구하기

 

 

❗ 결과

   👉 테스트 통과

 

 

✔ 소스코드

package lv2;

import java.io.IOException;
import java.util.ArrayList;

public class Solution {  // 카펫
	static class Info {
		int height;
		int width;
		
		public Info(int height, int width) {
			this.height = height;
			this.width = width;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
//		int brown = 10;
//		int yellow = 2;
//		int brown = 8;
//		int yellow = 1;
		int brown = 24;
		int yellow = 24;
		
		System.out.println(Arrays.toString(solution(brown, yellow)));
	}
	
	private static int[] solution(int brown, int yellow) {
		int[] answer = new int[2];
		ArrayList<Info> info = new ArrayList<>();
		
		int yh = 1;
		int yw = yellow/yh;
		while(yh <= yw) {
			info.add(new Info(yh, yw));
			yh += 1;
			yw = yellow/yh;
		}

		for (int i = 0; i < info.size(); i++) {
			if((info.get(i).width + 2)*2 + info.get(i).height*2 == brown) {
				answer[0] = info.get(i).width+2;
				answer[1] = info.get(i).height+2;
			}
		}
		
		return answer;
	}

}

 

이번 문제는 Lv2라기엔 생각보다 쉬웠던 문제

정답을 맞추고 다른 사람들의 풀이를 보았는데 수학적으로 접근한 사람들이 많았다는 것이 신기했고

나도 한번 더 생각해보게 되는 문제였다.