#1940: 주몽

풀이방법

사용된 것:

정렬

 

2022.08.12

재료가 N가지 있고 각 재료의 번호는 서로 겹치지 않는다.

재료 두 개를 골라 두 재료의 번호의 합이 M이 되는 경우의 수를 구하는 문제이다.

 

여러 가지 방법으로 풀 수 있는데 나는 아래와 같이 풀었다.

 

재료번호들을 오름차순 정렬한 뒤, (내림차순으로 정렬해도 됨)

0번 인덱스에 위치한 수를 좌항으로 잡고,

좌항보다 뒤의 인덱스에 위치한 수들을 우항 후보로 간주한다.

우항 후보들을 하나하나 검사해보며

좌항과의 합이 M이 되는 수가 존재하는지 판별한다.

 

그러한 수가 존재한다면,

정답의 값을 1 증가시킨 뒤, 현재의 좌항의 다음 수를 새로운 좌항으로 설정한 뒤 위의 과정을 반복한다.

 

코드

Java(2022.08.12)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//값 읽어오기
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		int[] nums = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) nums[i] = Integer.parseInt(st.nextToken());
		
		//고유번호들을 정렬하기
		Arrays.sort(nums);
		
		//정답 구하기
		int answer = 0;
		for(int i=0; i<n-1; i++) {
			for(int j=n-1; j>i; j--) {
				if(nums[i]+nums[j] == m) {
					answer++;
					break;
				}
			}
		}
		
		//정답 출력
		System.out.print(answer);
	}

}