[백준] 20444번: 색종이와 가위 (파이썬/Python) - 이진탐색

2022. 12. 9. 23:20·Algorithm (PS)
728x90

https://www.acmicpc.net/problem/20444

 

20444번: 색종이와 가위

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

www.acmicpc.net

i) 규칙 찾기 

n=4일때 가능한 모든 경우를 보면 
(col, row) = (0, 4), (1, 3), (2, 2) (3, 1), (4, 0) 이다 
근데 column , row 구분을 안해줘도 되는 이유가, 만들어지는 색종이의 개수만 확인하면 되기 때문이다. -> 즉 0 부터 n//2 까지의 경우만 확인해주면 시간을 줄일 수 있다. 

만들어 지는 색종이의 개수는 (col+1) * (row+1) 이다. 

또한 찾을 수 있는 규칙은, column 개수와 row의 개수 차이가 클수록 만들어지는 색종이의 개수가 줄어들고, column 개수와 row 개수 차이가 작을 수록 만들어지는 색종이의 개수가 증가한다.

ii) binary search 적용하기 
start, end 의 중간 값인 mid와 target값을 비교한다. 
이 문제의 경우 만들어진 색종이의 개수를 확인해 주어야 하므로, 위에서 찾아낸 공식에 의하면 

(mid+1) * (n-mid+1) = 색종이의 개수    이다. 

색종이의 개수가 target보다 크면, 가로와 세로 개수의 차이를 늘려야 한다.
row 값을 mid-1로 갱신해 준다. (binary search 에서 흔히 end에 해당)

반대로 색종이의 개수가 target보다 작으면, 가로와 세로 개수의 차이를 줄여서 box의 개수를 늘리는 col, row 쌍을 찾아야 한다. 
col 값을 mid+1로 갱신해준다. 

import sys

input = sys.stdin.readline

n, target = map(int, input().split())
flag = False

def binary_search():
    global flag
    col = 0 # start
    row = n // 2 # end ---> n=4 일 때 (0, 4), (1, 3), (2, 2) 이므로 n//2까지만 탐색해도 모든 케이스 확인 가능 !
    while col <= row:
        mid = (row+col)//2
        box = (mid+1) * (n-mid+1)
        if box == target:
            print("YES")
            flag = True
            break
        if box < target: # 칸을 늘리기 위해서는 가로와 세로 개수의 차이를 줄여야 한다.
            col = mid+1
        else:
            row = mid -1
             # 칸을 줄이기 위해서는 가로와 세로 개수의 차이를 늘려야 한다.

binary_search()
if not flag:
    print("NO")
728x90

'Algorithm (PS)' 카테고리의 다른 글

[백준] 13913번 : 숨바꼭질 4 (파이썬/Python) - BFS 풀이  (0) 2022.12.10
[백준] 22869번: 징검다리 건너기 small (파이썬/Python) - DP  (0) 2022.12.10
[백준] 20164번 : 홀수 홀릭 호석 (파이썬/Python) - 구현, 브루트포스  (0) 2022.12.09
[백준] 1253번 : 좋다 (파이썬/Python)  (0) 2022.12.09
[백준] 1890번 점프 (파이썬/Python) - DP  (0) 2022.12.09
'Algorithm (PS)' 카테고리의 다른 글
  • [백준] 13913번 : 숨바꼭질 4 (파이썬/Python) - BFS 풀이
  • [백준] 22869번: 징검다리 건너기 small (파이썬/Python) - DP
  • [백준] 20164번 : 홀수 홀릭 호석 (파이썬/Python) - 구현, 브루트포스
  • [백준] 1253번 : 좋다 (파이썬/Python)
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (612)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (29)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (4)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • 백트래킹
  • dfs
  • 백준
  • 카카오코딩테스트
  • 빅데이터
  • 프로그래머스
  • 코딩테스트
  • Databricks
  • ansible
  • docker
  • 알고리즘
  • EC2
  • 운영체제
  • 쿠버네티스
  • dp
  • 데이터엔지니어링
  • 파이썬
  • SPARK
  • Swift
  • Kubernetes
  • 데이터엔지니어
  • Leetcode
  • 데이터브릭스
  • 클라우드
  • BFS
  • 스파크
  • AWS
  • 리눅스
  • python
  • linux

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[백준] 20444번: 색종이와 가위 (파이썬/Python) - 이진탐색
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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