프로그래머스 카펫

Cloud_ Ghost·2024년 6월 11일

Python

목록 보기

11/15

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

코딩테스트 연습 > 완전탐색 > 카펫
풀이 : Python

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

※ 공지 - 2020년 2월 3일 테스트케이스가 추가되었습니다.
※ 공지 - 2020년 5월 11일 웹접근성을 고려하여 빨간색을 노란색으로 수정하였습니다.

col = 세로
row = 가로

다른것보다 문제의 조건을 정확히 이해하고 접근하는게 가장 중요한 문제이다.

왜 col은 3으로 정해놓는걸까?

아래의 그림과 같은 경우가 가장 최소한으로 모든 조건을 맞추는 경우이다.

col이 3보다 작은 경우라면 아래의 그림과 같이 갈색이 노란색을 둘러싸을 수 없게 된다.

그렇기 때문에 문제의 조건인 노란색을 둘러 싸기 위해서는 col=3이라는 값을 지켜야만 하는 것이다.

왜 "total에서 col을 나눈 나머지가 0이라면" 조건을 넣는걸까?

세로 길이 조건 확인 (if total % col == 0:)
total이 col로 나누어 떨어지는지 확인한다.
즉, col이 total의 약수인지 확인하는 것이다. 왜냐하면 col이 total의 약수일 때 col이 가능한 세로의 길이가 되기 때문이다.
가령 brown=8, yellow=1, total=9인 예시 상황에서 col=3이 아니라 col=4가 된다면 사각형이 만들어질 수 없다.

위 그림과 같이 col=4가 된다면 brown=12, yellow=4가 되어야 한다. 반드시 col은 total의 약수가 되어야만 가능한 가로의 길이가 되는 것이다.

정리하자면 total % col == 0이 참이라면, col은 가능한 세로 길이가 된다.

무한 루프 (while True:)
조건 없이 무한 루프를 시작합니다. 적절한 가로와 세로 길이를 찾을 때까지 계속해서 실행된다.

가로 길이 계산 (row = total // col)

total을 col로 나누어 가로 길이 row를 계산한다.
문제의 상황을 예시로 brown=8, yeloow=1, total=9일 때 row=3, col=3이다.
즉 3 = 9 // 3인것이다.
이외에 brown=12, yellow=4, total=16일 때 row=4, col=4이다.
즉, row = total // col을 만족해야 row 값을 구할 수 있다는 것이다.
만족하지 못 하는 경우를 예로 들자면 brown=8, yellow=1, total=9일 때 row=4,가 된다면 마찬가지로 조건을 만족하는 사각형을 만들 수 없다.
row=4가 된다면 total=16, col=4일때 조건을 만족하는 사각형을 만들 수 있다.

노란 타일 조건 확인

(if ((col - 2) * (row - 2)) == yellow:)
카펫의 내부 노란 타일 영역의 타일 수가 주어진 yellow와 같은지 확인한다.
col - 2는 갈색 타일로 둘러싸인 세로 길이, row - 2는 가로 길이이다.
아래의 그림과 같이 row=4, col=4인 경우라고 할 때, yellow의 넓이는 2 x 2=4 이다.
그렇다면 row와 col을 이용해서 yellow의 넓이를 어떻게 구할 수 있을까? 에 대한 답으로 총 col과 row의 길이를 각 2씩 빼면 된다.
왜냐하면 갈색 타일과 노란색 타일을 모두 합한 큰 사각형의 경우 갈색 타일이 노란색 타일을 한 칸의 크기로 둘러 싼 형태이다.
노란색 타일의 끝에 갈색 타일이 붙어있으므로 갈색 타일을 제거하려면 큰 사각형의 가로와 세로에 1씩 1씩 총 2를 각각 빼주면 된다.

정리하자면 ((col - 2) * (row - 2)) == yellow가 참이라면,
올바른 가로와 세로 길이를 찾은 것이다.

정답 저장 및 루프 종료

(answer.append(row), answer.append(col), break)
row와 col을 answer 리스트에 추가한다.
break 문을 사용하여 루프를 종료힌다.

세로 길이 증가

(col += 1)
루프가 종료되지 않았다면, 세로 길이 col을 1 증가시켜 다음 가능한 세로 길이를 검사한다.

# 성공한 코드
def solution(brown, yellow):
    answer = []
    total = brown + yellow
    col = 3
    
    while True:
        if total % col == 0:
            row = total // col
            if ((col - 2) * (row - 2)) == yellow:
                answer.append(row)
                answer.append(col)
                break
        col += 1
    
    return answer

brown = int(input("brown 개수 : "))
yellow = int(input("yellow 개수 : "))

result = solution(brown, yellow)
print(f"가로 길이: {result[0]}, 세로 길이: {result[1]}")

# 실패한 코드
def solution(brown, yellow):
    area_garo = 0
    area_sero = 0
    all_sum = yellow + brown
    all_sum == area_garo * area_sero

    area_garo = brown//2 - area_sero + 2
    area_sero = brown//2 - area_garo + 2

    if area_garo < area_sero :
        return 0
    return area_garo, area_sero


brown = int(input("brown 개수 : "))
yellow = int(input("yellow 개수 : "))


result = solution(brown, yellow)
print(f"가로 길이: {result[0]}, 세로 길이: {result[1]}")