엠케이의 개발공간

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장에게 철기군이 입을 갑옷을 만들라고 명령했다. 야철대장은 주몽의 명령에 따르기 위해 연구에 착수하던 중 갑옷을 만드는 재료들은 가각 고유한 번호가 있고, 갑옷은 2개의 재료로 만드는 데 2가지 재료의 고유한 번호를 합쳐 M (1 <= M <= 10,000,000)이 되면 갑옷이 만들어진다는 사실을 발견했다. 야철대장은 자신이 만들고 있는 재료로 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 야철대장의 궁금증을 풀어 주기 위해 N (1 <= N <= 15,000)개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

1번째 줄에 재료의 개수 N (1 <= N <= 15,000), 2번째 줄에 갑옷을 만드는 데 필요한 수 M(1 <= M <= 10,000,000)이 주어진다. 3번째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수다.

출력

1번째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 1

6	// 재료의 개수
9	// 갑옷이 완성되는 번호의 합
2 7 4 1 5 3	// 재료들

예제 출력 1

2

코드

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

public class P1940_주몽의명령 {
	
	public static void main(String[] args) throws IOException {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());        
        int M = Integer.parseInt(br.readLine());
        
        int[] A = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < N; i++){
        	A[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(A);
        
        int st_index = 0;
        int ed_index = N - 1;
        int count = 0;
        
        while(st_index < ed_index){
        
        	if(A[st_index] + A[ed_index] < M){
            	st_index++;
            
            } else if(A[st_index] + A[ed_index] > M){
            	ed_index--;
            
            } else {
            	count++;
                st_index++;
                ed_index--;
            }
        
        }    
    }    
}

투 포인터 이동 원칙으로 접근하면 된다.

어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1<=N<=10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이때 사용하는 자연수는 N 이여야 한다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5 이다. 반면, 10을 나타내는 방법은 10, 1+2+3+4이다. N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오.

입력

1번째 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 연속된 자연수의 합으로 나타내는 가짓수를 출력한다.

예제 입력 1

15 // N

예제 출력 1

4

코드

import java.util.Scanner;

public class P2018_연속된자연수의합 {
	
	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		int count = 1;
		int start_index = 1;
		int end_index = 1;
		int sum = 1;
		
		while(end_index != N) {
			
			if(sum == N){
				count++;
				end_index++;
				sum = sum + end_index;
			
			} else if(sum > N){
				sum = sum - start_index;
				start_index++;
			
			} else {
				end_index++;
				sum = sum + end_index;
			}
			
		}
		System.out.println(count);
		
	}
}

투 포인터 이동 원칙을 이용해서 접근하면 되는 문제이다.

1~15 을 1번째부터 start_index, end_index 로 시작하고, sum 이 15가 될 때까지 end_index 를 이동시키고, 15가 되는 경우 start_index를 이동한다.

start_index -->
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
end_index -->

투 포인터 이동 원칙

sum > N : sum = sum - start_index; start_index++;

sum < N : end_index++; sum = sum + end_index;

sum == N : end_index++; sum = sum + end_index; count++;

Reference

백준의 올라인 저지 2018번