[ProblemSolving] 백준 - 20444 색종이와가위 (수학)
문제 링크
문제 설명
오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!
색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!
색종이를 자를 때는 다음과 같은 규칙을 따른다.
색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
이미 자른 곳을 또 자를 수 없다.
분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.
입력
첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)
출력
첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다
예제 입력1
4 9
예제 출력1
YES
나의 풀이
가로로 자르는 횟수 + 세로로 자르는 횟수 = n일때,
(가로로 자르는 횟수+1)x(세로로 자르는 횟수 +1)= 조각의 수가 된다.
i가 가로로 자르는 횟수일 때,(i+1)*((n-i)+1) 이 k조각과 같은지 확인
하여 출력하면 된다.
이렇게 풀면 시간 초과는 발생하지 않지만 느리다. 많이 느리다. (pypy로 채점)
이분 탐색으로 구현하면 훨씬 문제를 빠르게 해결할 수 있다. 이 코드는 다음에 첨부
코드
n, k = map(int, input().split())
for i in range(n//2+1):
if (i+1)*((n-i)+1) == k:
print("YES")
break
else:
print("NO")
Author And Source
이 문제에 관하여([ProblemSolving] 백준 - 20444 색종이와가위 (수학)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@redcarrot01/ProblemSolving-백준-20444-색종이와가위-수학저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)