문제
N개의 재료가 주어졌을 때, 두 재료의 번호 합이 M이 되는 쌍의 수를 구하라.
입력
첫째 줄에 N, 둘째 줄에 M, 셋째 줄에 N개의 재료 번호가 주어진다.
출력
합이 M인 쌍의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 9 2 7 4 1 5 3 | 2 |
풀이
모든 쌍을 탐색하여 합이 M인 경우를 카운트한다.
- 각 재료 i에 대해 i+1부터 N까지의 재료 j와 합을 확인한다
material[start] + material[end]가 M이면 카운트를 증가시키고 탈출한다- 모든 쌍을 확인한 뒤 결과를 출력한다
핵심 아이디어: 이중 루프로 모든 (i, j) 쌍을 탐색하여 합이 M인 쌍을 센다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day349BOJ1940주몽 {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int m = Integer.parseInt(reader.readLine());
int[] material = new int[n];
StringTokenizer st = new StringTokenizer(reader.readLine());
for (int i = 0; i < n; i++) {
material[i] = Integer.parseInt(st.nextToken());
}
int cnt = 0;
for (int start = 0; start < n; start++) {
int sum = 0;
int end = start + 1;
while (end < n) {
sum = material[start];
sum += material[end++];
if (sum == m) {
cnt++;
break;
}
}
}
System.out.println(cnt);
}
}복잡도
- 시간: O(N^2) - 모든 쌍 탐색
- 공간: O(N)