엠케이의 개발공간

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장에게 철기군이 입을 갑옷을 만들라고 명령했다. 야철대장은 주몽의 명령에 따르기 위해 연구에 착수하던 중 갑옷을 만드는 재료들은 가각 고유한 번호가 있고, 갑옷은 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번

문제

수 N 개가 주어졌을 때 i 번째 수에서 j 번째 수까지의 합을 구하는 프로그램을 작성하시오

입력

1번째 줄에 수의 개수 N (1~100,000), 합을 구헤야 하는 횟수 M(1~100,000), 2번째 줄에 N개의 수가 주어진다. 각 수는 1,000 보다 작거나 같은 자연수다. 3번째 줄부터는 M개의 줄에 합을 구해야 한느 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i 번째 수에서 j 번째 수까지의 합을 출력한다.

예제 입력

5 3		//데이터의 개수, 질의 개수
5 4 3 2 1	//구간 합을 구할 대상 배열
1 3
2 4
5 5

예제 출력

12
9
1

먼저, 합의 배열을 만들자.

A : 보기 배열

S : 합 배열

S[ i ] = S[ i -1 ] + A [ i ]

구간 i ~ j 를 구하는 구간 합 공식으로 정답을 출력하자.

공식 : S[ j ] - S[ i - 1]

코드

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

public class P11659_구간합구하기 {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		
		int suNo = Integer.parseInt(stringTokenizer.nextToken());
		int quizNo = Integer.parseInt(stringTokenizer.nextToken());
		
		long[] S = new long[suNo+1];
		
		stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		
		for(int i = 1; i <= suNo; i++){
			S[i] = S[i-1] + Integer.parseInt(stringTokenizer.nextToken());
		}
		
		for(int q = 0; q < quizNo; q++) {
			
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			
			int i = Integer.parseInt(stringTokenizer.nextToken());
			int j = Integer.parseInt(stringTokenizer.nextToken());
			
			System.out.println(S[j]-S[i-1]);
			
		}
	}
}

Reference

백준 온라인 저지 11659번

문제

N 개의 숫자가 공백 없이 써 있다. 이 숫자를 모두 합해 출력하는 프로그램을 작성하시오.

입력

1번째 줄에 숫자의 개수 N(1 <= N <= 100), 2번째 줄에 숫자 N 개가 공백 없이 주어진다.

출력

입력으루 주어진 숫자 N 개의 합을 출력한다.

예제 입력 1

1 // 숫자의 개수
54321 // 공백 없이 주어진 N 개의 숫자

예제 출력 1

15

코드

import java.util.Scanner;

public class P11720_숫자의합 {
	
	public static void main(String[] args) {		
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		String sNum = sc.next();
		char[] cNum = sNum.toCharArray();
		int sum = 0;
		for (int i = 0; i < cNum.length; i++){
			sum += cNum[i] - '0';
		}
		
		System.out.println(sum);
	}
}

결과

Reference

백준 온라인 저지 11720번

자기개발로 알고리즘 공부를 시작해려고 한다.

큰 맘 먹고 알고리즘 코딩 테스트 책을 샀는데....(굳이 필요했을까? 라는 생각도 들지만.. 한 권 있으면 좋으니까 ㅎㅎ)

취준할 때는 백준 사이트를 애용했었는데, 요즘에는 다른 곳도 많이 사용하는 것 같다.

기업에서 코딩 테스트로 이용할 수 있는 사이트도 많이 생긴 것 같다.

이 책에 있는 내용을 한 바퀴 쭉 돌고, 여러 사이트를 돌면서 스스로 풀어봐야겠다.

그럼 시작~~