띠용

문제: 백준 온라인 저지 2018번

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력: 첫 줄에 정수 N이 주어진다.

출력: 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());
        long n = Long.parseLong(input.nextToken());
        
        long start = 1;
        long end = 2;
    	long sum = start;
    	long count = 1;
        
    	while(start < n && end <= n) {
    		if(sum < n)
    			sum += end++;
    		else if(sum > n){
    			sum -= start;
    			start++;
    		}
    		else {
    			count++;
    			sum -= start;
    			start++;
    		}
    	}
    	System.out.println(count);
    }
}

추가 설명

문제: 백준 온라인 저지 10986번

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력: 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103), 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력: 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer input = new StringTokenizer(br.readLine());
    	
    	int N = Integer.parseInt(input.nextToken());
    	int M = Integer.parseInt(input.nextToken());
    	int[] mod = new int[N+1];
    	long[] rest = new long[M];
    	long count = 0;
    	
    	input = new StringTokenizer(br.readLine());
    	for(int i = 1; i <= N; i++) {
    		int num = Integer.parseInt(input.nextToken());
    		mod[i] = (mod[i - 1] + num) % M;
    		rest[mod[i]]++;
    	}
    	count = rest[0];
    	
    	for(int i = 0; i < M; i++) {
    		count += (rest[i] * (rest[i]-1))/2;
    	}
    	System.out.println(count);
    }
}

추가 설명

원리 1) 구간 내 수들의 합을 M으로 나눈 나머지는 구간 내 수들의 나머지의 합의 나머지와  동일하다.

     (A + B) % M ==  ((A % M) + (B % M)) % M 

원리 2) S[i]을 M으로 나눈 나머지와 S[j]의 나머지가 동일하면 S[j] - S[i]은 M으로 나누어 떨어진다.

     if((S[i] % M) == (S[j] % M))

          (S[j] - S[i]) % M == 0;

원리 3) 구간의 합이 M으로 나누어 떨어지는 구간의 개수

: 나머지가 같은 합 배열들 중에서 2개를 뽑는 모든 경우의 수이다.

문제: 백준 온라인 저지 11660번

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력: 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력: 총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer input = new StringTokenizer(br.readLine());
    	int n = Integer.parseInt(input.nextToken());
    	int m = Integer.parseInt(input.nextToken());
    	
    	int[][] arr = new int[n + 1][n + 1];
    	int[][] dp = new int[n + 1][n + 1];
    	
    	//dp테이블
    	for(int i = 1; i <= n; i++) {
	    	input = new StringTokenizer(br.readLine());
    		for(int j = 1; j <= n; j++) {
    	    	arr[i][j] = Integer.parseInt(input.nextToken());
    	    	dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
    		}
    	}
    	
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	for(int i = 0; i < m; i++) {
        	input = new StringTokenizer(br.readLine());
        	int x1 = Integer.parseInt(input.nextToken());
        	int y1 = Integer.parseInt(input.nextToken());
        	int x2 = Integer.parseInt(input.nextToken());
        	int y2 = Integer.parseInt(input.nextToken());
        	int result = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
        	bw.write(Integer.toString(result));
        	bw.newLine();
    	}
    	bw.flush();
    	bw.close();
    }
}

추가 설명

- 배열은 선언한 데이터 타입에 따라 기본값이 결정된다

- dp 테이블을 사용하여 미리 누적합을 준비해둔다.

- dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j];

- (x1, y1), (x2, y2) 구간합 = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]

문제: 백준 온라인 저지 11659번

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력: 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

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

제한

1 ≤ N ≤ 100,000

1 ≤ M ≤ 100,000

1 ≤ i ≤ j ≤ N

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer input = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(input.nextToken());
        int m = Integer.parseInt(input.nextToken());
        
        //합 배열
        int[] arr = new int[n + 1];
        arr[0] = 0;        
        input = new StringTokenizer(bf.readLine());
        for(int i = 1; i <= n; i++){
            arr[i] = arr[i - 1] + Integer.parseInt(input.nextToken());
        }
        
        //구간 합
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int k = 0; k < m; k++){
            input = new StringTokenizer(bf.readLine());
            int i = Integer.parseInt(input.nextToken());
            int j = Integer.parseInt(input.nextToken());
            bw.write(Integer.toString(arr[j] - arr[i-1]));
            bw.newLine();
        }
        
        bw.flush();
        bw.close();
    }
}

추가 설명

: 구간 합 알고리즘을 사용하면 시간복잡도를 감소시킬 수 있다. 또한 Scanner를 사용하면 시간 초과가 발생할 우려가 있기 때문에 Buffer를 사용한다.

문제: 백준 온라인 저지 1546번

세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다.

예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다.

세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오.

입력: 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다.

출력: 첫째 줄에 새로운 평균을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-2 이하이면 정답이다.

코드

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] grade = new int[size];
        int max = 0;
        long sum = 0;
	    
        for(int i = 0; i < size; i++){
            grade[i] = sc.nextInt();
            if(max < grade[i])
                max = grade[i];
        }
        for(int i = 0; i < size; i++){
            sum += grade[i];
        }
        double answer = (double)sum / max * 100 / size;
        System.out.println(answer);
    }
}

추가 설명

: 모든 점수를 공통적으로 변환시킬 것이기 때문에 변환된 점수를 하나하나 구할 필요가 없고 마지막에 모든 점수를 합해서 한 번만 변환시켜주면 간단하다.

문제: 백준 온라인 저지 11720번

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

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

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

코드

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    	int size = sc.nextInt();
        String number = sc.next();
        int sum = 0;
        
        for(int i = 0; i < size; i++){
            sum += number.charAt(i) - '0';
        }
        System.out.println(sum);
    }
}

추가 설명

: 문자 '1'은 아스키코드 값이 49이다. 즉 문자와 숫자의 코드값 차이는 48이므로 문자에서 48을 빼주면 숫자화시킬 수 있다.

숫자 48 == '0' 아스키코드 값

'1' 아스키코드 값 == 49, 숫자 1 == '1' - 48 == '1' - '0'

'2' 아스키코드 값 == 50, 숫자 2 == '2' - 48 == '2' - '0'