[프로그래머스/완전탐색] L2: 카펫 - 파이썬

2022. 5. 20. 21:25· Problem Solving/CT-Python
목차
  1. 문제
  2. 풀이
  3. 다른 풀이

문제

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

 

코딩테스트 연습 - 카펫

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

programmers.co.kr

 

풀이

문제를 다 풀었지만 테스트케이스 4번에서 자꾸 오류가 났었는데

(이 사람도 나와 같은 문제를 겪었다. https://programmers.co.kr/questions/6882)

30분동안 헤메다가 답을 찾았다. (여기를 참조함 https://programmers.co.kr/questions/11500)

 

위와 같이 가로가 가장 큰 순서대로 정렬하여 가로가 가장 큰 값을 결과로 도출하면 된다.

(첫번째 출력은 노란색이 나올 수 있는 경우의 수, 두번째는 전체 크기(노란색+갈색)이 나올 수 있는 경우의 수

세번째는 조건을 만족하는 경우의 수 이다)

 

문제에 답에 대한 정확한 명시가 있었으면 하면 바램이다.

(다음 풀이는 best-case가 아니므로 이런식으로 풀이를 할 수 있구나 하고 참고하시면 되겠습니다.)

def solution(b, y):
    e = b + y # 노란색, 갈색 전체 합
    yList = []
    eList = []

	# 노란색 크기가 나올 수 있는 경우의 수 구해서 리스트에 저장
    for i in range(1,y+1):
        if y % i == 0:
            if i >= y//i:
                yList.append([i, y//i])

	# 노란색, 갈색 합친크기가 나올 수 있는 경우의 수 구해서 리스트에 저장
    # 문제에서 세로의 길이가 3 미만이면 노란색 부분은 나올 수 없음
    for j in range(3, e+1):
        if e % j == 0:
            if j >= e//j and e//j >=3:
                eList.append([j, e//j])
    
    # 결과를 저장할 리스트 선언
    result = []
    # 전체 크기의 경우의수가 저장된 리스트에서 노란색 크기가 나올 수 있는 경우의 수 구함
    for i in range(len(eList)):
        for j in range(len(yList)):
        	# 전체 크기 경우의 수 중에 한쪽 면이 노란색 크기의 면보다 -2가 되는지 확인해야함
            # 이를 만족하지 않으면 갈색 크기 안에 노란색 크기가 들어갈 수 없음
            if eList[i][0] >= yList[j][0]+2 and eList[i][1] >= yList[j][1]+2:
                result.append(eList[i])
    # 결과들 중 가로의 길이가 제일 긴 순서대로 정렬
    result.sort(reverse = True)
    # 맨 앞의 원소가 우리가 찾고자 하는 값
    answer = result[0]

    return answer

 

다른 풀이

수학적으로 접근하여 푸는 방법이 있다.

def solution(brown, yellow):
    total = brown + yellow
    for weight in range(total, 2, -1):
        if total % weight == 0:
            height = total // weight 
            if yellow == (weight-2) * (height-2):
                return [weight, height]

카펫 넓이 = brown + yellow = width * height

외부 사각형 갯수(brown) = 2w + 2h + 4

내부 사각형 갯수(yellow) = (x-2) * (y-2)

'Problem Solving > CT-Python' 카테고리의 다른 글

[백준/DP] 1463: 1로 만들기 - 파이썬  (0) 2022.05.24
[SWEA/구현] 10570[D3]: 제곱 팰린드롬 수 - 파이썬  (0) 2022.05.23
[백준/구현] 13904: 과제 - 파이썬  (0) 2022.05.18
[백준/DFS-BFS] 7576: 토마토 - 파이썬  (0) 2022.05.18
[백준/DFS-BFS] 11403: 경로 찾기 - 파이썬  (0) 2022.05.17
  1. 문제
  2. 풀이
  3. 다른 풀이
'Problem Solving/CT-Python' 카테고리의 다른 글
  • [백준/DP] 1463: 1로 만들기 - 파이썬
  • [SWEA/구현] 10570[D3]: 제곱 팰린드롬 수 - 파이썬
  • [백준/구현] 13904: 과제 - 파이썬
  • [백준/DFS-BFS] 7576: 토마토 - 파이썬
White Han
White Han
Software Developer
White Han
sudo apt-get happiness
White Han
전체
오늘
어제
  • 분류 전체보기 (183)
    • Language (35)
      • Java (17)
      • Java-Weekly-study (0)
      • Python (18)
    • BackEnd (11)
      • Server (2)
      • Spring (3)
      • Spring Security (0)
      • JDBC (1)
      • NodeJS (2)
      • LINUX (3)
    • DataBase (10)
      • MySQL (5)
      • MongoDB (4)
      • Oracle (1)
    • Infra (4)
      • Docker (4)
    • CS (38)
      • OS (38)
    • Problem Solving (79)
      • Algorithm (8)
      • CT-Java (30)
      • CT-Python (41)
    • IDE (1)
      • eclipse (1)
      • vscode (0)
    • Etc. (3)
      • Git (1)
      • TDD, Refactor, CleanCode (1)
      • Conference (1)
    • 기록 (2)
      • 후기 (1)
      • 프로젝트 회고록 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

공지사항

  • 방문해 주셔서 감사합니다.

인기 글

태그

  • 싸피 합격
  • 운영체제
  • 자바스크립트 개념
  • 자바 inheritance
  • 24인치 모니터 추천
  • 싸피
  • 알파스캔 모니터
  • 운영체제 구조
  • 운영체제 역할
  • 사무용 모니터 추천
  • 자바스크립스 식별자 종류
  • 사무용 모니터
  • 자바 this
  • SSAFY
  • 싸피 후기
  • 자바 super
  • OS
  • javascript identifier
  • Java Inheritance
  • javascript
  • Java this
  • 알파스캔 AOC 24B1X
  • 프로세서
  • 자바스크립트 식별자
  • 자바스크립트
  • Java super
  • 프로세스
  • java
  • AOC 24B1X
  • 싸피8기

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
White Han
[프로그래머스/완전탐색] L2: 카펫 - 파이썬
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.