풀이 방법
n 번의 가위질로 만들 수 있는 조각의 개수는 (가로 + 1) * (세로 + 1) 개 이다.
이 문제는 경우의 수가 많아 이분탐색을 사용해서 풀이했다.
가로, 세로 갯수가 같을 때 조각의 개수가 가장 많이 나오게 되어서 이분탐색의 right 값을 N/2로 시작했다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long N = Long.parseLong(st.nextToken());
long K = Long.parseLong(st.nextToken());
long left = 0L;
long right = N / 2;
while (left <= right) {
long mid = (left + right) / 2;
long result = (mid + 1) * (N - mid + 1);
if (result == K) {
System.out.println("YES");
return;
} else if (result > K) {
right = mid - 1;
} else if (result < K) {
left = mid + 1;
}
}
System.out.println("NO");
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
택배 - 1719번 (0) | 2021.10.26 |
---|---|
점수따먹기 - 1749번 (0) | 2021.10.25 |
네트워트 연결 - 1922번 (0) | 2021.10.22 |
오리 - 12933번 (0) | 2021.10.22 |
운동 - 1956번 (0) | 2021.10.21 |