BOJ_1637_날카로운 눈 (Java)
BOJ_1637_날카로운 눈 (Java)
[Platinum IV] 날카로운 눈 - 1637
성능 요약
메모리: 14916 KB, 시간: 136 ms
분류
이분 탐색, 매개 변수 탐색
제출 일자
2025년 2월 8일 22:44:20
문제 설명
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다.
어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제는 다음과 같다.
정수가 여러 개 모여 있는 정수더미가 있다. 그 안에 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 모두 짝수개 존재한다. 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다.
근데 멍멍이가 문제를 전달해 주려다가 생각해보니 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 되는 것이다. 그래서 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성하시오.
입력
첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 안에 있다는 것을 나타낸다. A, B, C는 1보다 크거나 같고 2,147,483,647보다 작거나 같은 정수이다. 정수더미는 N개의 입력이 나타내는 정수들을 모두 포함한다.
출력
첫째 줄에 정수 두 개를 출력하는데, 첫 번째는 홀수개 존재하는 정수를 출력하고, 두 번째는 그 정수가 몇 개 들어있는지 출력한다. 만약 홀수개 존재하는 정수가 없다면 NOTHING을 출력한다.
문제 풀이
제한이 매우 크지만 모두 탐색해야하기 때문에 파라매트릭 서치를 사용했다.
mid를 이분탐색으로 갱신하면서 mid까지의 개수를 기준으로 짝수개면 mid 초과 부분에 홀수개가 있단것이므로 오른쪽 구간을 선택, 반대로 홀수면 홀수가 나왔단 의미이므로 왼쪽구간을 선택했다.
특정 숫자까지 개수가 몇개인지는 그림과 같은 수식을 통해 체크할 수 있었고 특정 숫자(mid)에서의 개수는 mid까지의 개수 - (mid-1)까지의 개수로 셀 수 있었다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package BOJ_1637_날카로운눈;
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N;
static long res;
static boolean flag = false;
static int[][] board; // [A, C, B] 저장
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
// br = new BufferedReader(new InputStreamReader(System.in));
br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1637_날카로운눈/input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
board = new int[N][3];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
board[i][0] = Integer.parseInt(st.nextToken());
board[i][1] = Integer.parseInt(st.nextToken());
board[i][2] = Integer.parseInt(st.nextToken());
}
long left = 1;
long right = 2147483647;
while(left<=right) {
long mid = left + (right - left)/2;
long cnt = getCnt(mid);
if(cnt % 2 == 0) left = mid + 1;
else {
res = mid;
right = mid - 1;
if(!flag) flag = true;
}
}
if(!flag) sb.append("NOTHING");
else {
long ans = getCnt(res) - getCnt(res-1);
sb.append(res).append(" ").append(ans);
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
private long getCnt(long mid) { // mid보다 작거나 같은 수들의 총 개수
if(mid < 1) return 0;
long sum = 0;
long A, B, C;
for(int i=0; i<N; i++){
A = board[i][0];
C = board[i][1];
B = board[i][2];
if(mid < A) continue;
if(mid > C) sum += (C-A)/B + 1;
else sum += (mid-A)/B + 1;
}
return sum;
}
}
빠른 입출력 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package BOJ_1637_날카로운눈;
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main2 {
static class FastReader {
private final DataInputStream din;
private final byte[] buffer;
private int bufferPointer, bytesRead;
public FastReader() {
din = new DataInputStream(System.in);
buffer = new byte[16384];
bufferPointer = bytesRead = 0;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, buffer.length);
if (bytesRead == -1)
buffer[0] = -1;
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return neg ? -ret : ret;
}
}
static class FastWriter {
private final BufferedOutputStream bos;
public FastWriter() {
this.bos = new BufferedOutputStream(System.out);
}
public void print(Object object) throws IOException {
bos.write(object.toString().getBytes());
}
public void println(Object object) throws IOException {
print(object);
bos.write('\n');
}
public void flush() throws IOException {
bos.flush();
}
}
static StringBuilder sb = new StringBuilder();
static int N;
static long res;
static boolean flag = false;
static int[][] board; // [A, C, B] 저장
public static void main(String[] args) throws Exception {
new Main2().solution();
}
public void solution() throws Exception {
FastReader fr = new FastReader();
FastWriter fw = new FastWriter();
N = fr.nextInt();
board = new int[N][3];
for(int i=0; i<N; i++) {
board[i][0] = fr.nextInt();
board[i][1] = fr.nextInt();
board[i][2] = fr.nextInt();
}
long left = 1;
long right = 2147483647;
while(left<=right) {
long mid = left + (right - left)/2;
long cnt = getCnt(mid);
if(cnt % 2 == 0) left = mid + 1;
else {
res = mid;
right = mid - 1;
if(!flag) flag = true;
}
}
if(!flag) fw.println("NOTHING");
else {
long ans = getCnt(res) - getCnt(res-1);
fw.print(res);
fw.print(" ");
fw.println(ans);
}
fw.flush();
}
private long getCnt(long mid) { // mid보다 작거나 같은 수들의 총 개수
if(mid < 1) return 0;
long sum = 0;
long A, B, C;
for(int i=0; i<N; i++){
A = board[i][0];
C = board[i][1];
B = board[i][2];
if(mid < A) continue;
if(mid > C) sum += (C-A)/B + 1;
else sum += (mid-A)/B + 1;
}
return sum;
}
}
This post is licensed under
CC BY 4.0
by the author.