Life Study

문제: https://www.acmicpc.net/problem/1253

책에서 나오는 투 포인터 마지막 문제다. 책에서는 골드 3이라고 되어있는데, 현재는 골드 4로 내려갔다.
따끈따끈하게 실버로 올라온 뉴비에겐 솔직히 이 문제 너무 어려웠다.
책에 있는 풀이를 봐도 이해가 안됐다. 사실 한번 급하게 삽질을 끝낸 적은 있었는데,
다시 하려니까 같은 곳에서 해맨 것이다.

암튼 서론은 여기까지 하고 이제 본론으로 들어가자.
N을 입력받고 N개의 숫자들을 입력을 받고나서 이 숫자들끼리 서로 더해서 배열 안에 있는 요소가 되면
그게 문제에서 얘기하는 '좋은 수'인 것이다. 아 근데 자기 자신을 더해서 그 숫자가 나오는건 제외한다.
ex) 1+1 = 2, 2+2 = 4 ... 왜냐하면 문제에서 "수의 위치가 다르면 값이 같아도 다른 수이다."라고 했다.
이것을 대우로 뒤집어보면 "값이 달라도 같은수이면 수의 위치가 같다." 와 같은 문장이 된다.
결국 같은 수끼리는 더하면 안된다는 말이 문제에 내포되어있는 것이다.
다만 이건 필자같은 코린이들에게는 흐름이 좀 어려울 수 있으니, 그림으로 설명을 해보겠다.
N은 5이며 1 2 3 4 5 를 입력받았다고 가정하자.

그럼 이제 이 흐름들을 토대로 코드를 짜볼 시간이다.

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

public class BOJ_1253_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 1253
		
        //입력을 빨리 받기 위한 BufferedReader 클래스 객체 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //한 줄에 하나만 입력 받는다면 StringTokenizer 클래스를 이용한
        //문자열 파싱이 필요가 없음.
        //nums라는 배열 선언 -> 숫자들을 저장할 배열
		int N = Integer.parseInt(br.readLine());
		int nums[] = new int[N];
		
        //한 줄에 여러개의 숫자들을 입력받아야 하기 때문에 파싱이 필요해짐.
        //StringTokenizer 클래스 객체 선언해줌.
        //for문을 이용해서 배열에 파싱한 숫자들을 하나씩 저장해준다.
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //배열의 내용물을 정렬해준다. 투 포인터 알고리즘을 사용해야 하기 때문이다.
        //answer는 '좋은 수'의 개수를 카운팅하기 위한 변수다.
		Arrays.sort(nums);
		int answer = 0;
		
        //서로 더해서 나와야 하는 값을 target 변수로 설정했음.
        //target에 배열의 각 요소 값들이 저장되어야 하므로 for문으로 
        //while(투 포인터 반복문)을 감싸준다.
		for(int i=0; i<N; i++) {
			int target = nums[i];
			int start = 0, end = N-1;
			
            //투 포인터 알고리즘
			while(start < end) {
            	//sum은 반복문 안에서 값이 계속 바뀌어야 함.
                //sum과 target의 값을 비교해야 하기 때문.
				int sum = nums[start] + nums[end];
				
                //sum이랑 target이 같을 경우엔 start와 end를 한번 더 체크해준다.
                //그래야 자기 자신과 더해서 좋은 수를 찾지 않을 수 있기 때문이다.
				if(sum == target) {
					if(start != i && end != i) {
						++answer;
						break;
					} else if(start == i) {
						++start;
					} else {
						--end;
					}
				} else if(sum < target) {
                	//sum값이 target보다 작다면 값을 늘려줘야 하므로,
                    //start를 늘려준다.
					++start;
				} else {
                	//else라면 sum > target 경우밖에 남지 않는데,
                    //이는 sum의 값을 줄여줘야 하므로 end를 줄여준다.
					--end;
				}
			}
		}
		
        //for문과 while문에서 나온 후 answer를 출력해준다.
		System.out.println(answer);
	}
}

문제: https://www.acmicpc.net/problem/1940

수 들의 합 5를 클리어하고 단톡방에 계신 분들이 추천해주시는 몇몇 문제들을 푼 다음 풀게 되었던 문제다.
이 문제를 계기로 나는 투 포인터가 같은 방향에서  시작하는 것과 서로 다른 방향에서 진행하는 것에 대한 의문점을 갖게 되었다.
그 해답을 찾기 위해 용액이라는 문제를 풀게 되었던 것이다. 용액이 어떤 문제인지 궁금한 분들은 용액 글씨를 클릭해,
문제 풀이를 보면 될 것 같다.

서론은 이쯤에서 그만두고 이제 본론으로 넘어가보자.
문제를 먼저 분석해보자면, 재료의 개수가 N이고 갑옷을 만드는데에 필요한 수 M인데,
N개의 재료번호의 합이 M이 되는 것이 총 몇 개인지 물어보는 문제다.
사실 투 포인터는 배열을 정렬하는 로직이 필요한 알고리즘이다.
왜냐하면 더해지는 값과 목표값의 차이에 따라서 두 개의 포인터를 움직여야 하기 때문이다.
따라서 정렬을 해준 다음에 투 포인터 알고리즘을 이용해서 풀면 된다.
투 포인터 알고리즘에 대해서 잘 모르시는 분들은 해당글의 "투 포인터" 글씨를 클릭해주면 자세한 설명을 읽을 수 있을 것이다.

문제 풀이도 끝났으니, 이제 코드를 봐보자.

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

public class BOJ_1940_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 1940
		
        //숫자를 빨리 입력받기 위해서 BufferedReader 클래스 객체 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //BufferedReader 클래스는 한 줄씩 입력을 받고,
        //한줄에 하나의 숫자만 입력을 받는다면 StringTokenizer로 숫자들을 파싱할 이유가 없음.
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
        
        //재료의 번호들을 저장할 배열 선언
		int[] nums = new int[N];
		
        //한 줄에 여러 숫자들을 입력받으므로 StringTokenizer 클래스 객체 선언
		StringTokenizer st = new StringTokenizer(br.readLine());
        
        //입력받은 여러개의 숫자들을 각각 배열의 매 칸마다 저장함
		for(int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //오름차순으로 정렬해준다. 투포인터 알고리즘을 이용하기 위해서다.
		Arrays.sort(nums);
		
        //start는 투 포인터 시작 인덱스, end는 투 포인터 끝 인덱스,
        //answer는 nums[start] + nums[end]가 M이랑 같을 때를 카운트하는 변수다.
		int start = 0, end = N-1, answer = 0;
		
        //투 포인터 알고리즘
		while(start < end) {
        	//sum은 반복문이 돌 때마다 바뀌어야 하며,
            //sum에 대한 start와 end에 대한 연산을 줄이기 위해
            //sum을 반복문 안에다 선언하면서 초기화를 해준다.
			int sum = nums[start] + nums[end];
			
            //sum이랑 M이 같다면 +1해주고 start를 증가시켜서
            //다음 경우의 수로 넘어간다.
            		if(sum == M) {
				++answer;
				++start;
			} else if(sum < M) {
            	//sum보다 M이 크다면 이는 sum의 값을 늘려줘야 하므로,
                //start를 늘려준다.
				++start;
			} else {
            	//else라면 sum > M 경우만 남는데,
                //이는 sum의 값을 줄여줘야 하므로, end를 줄여준다.
				--end;
			}
		}
		
        //그렇게 반복문이 종료되면 answer를 출력해준다.
		System.out.println(answer);
	}

}

문제: https://www.acmicpc.net/problem/2018

책에서 투 포인터에 들어갈 때 가장 처음으로 나오는 문제다.
문제는.. 알고리즘이 매우 간단하다며 바로 실전 문제를 풀어보자는 말과 함께 등장하는 문제라는 것이다.
당황스럽지만 우리는 풀어야 한다.

문제를 보면 15를 표현하는 방법은 여러개가 있다고 한다. 7+8, 4+5+6, 1+2+3+4+5.
이 방법들이 총 몇 개인지 출력하면 되는 간단한 문제이다.
문제로는 간단하지만 막상 짜려고 하면 잘 모르겠는게 사실이니, 자세한 투 포인터의 개념은 "투 포인터" 글씨를 눌러주길 바란다.
배경색으로 입혀져있는 투 포인터 글씨들은 모두 그와 해당하는 글의 링크로 되어 있으니 참고 바란다.

그럼 이제 문제를 풀기 위해 어떤 개념이 필요한지 알았으니, 어떤 방식으로 짜야 하는가를 알아보자.
이 문제는 같은 방향에서 진행하는 투 포인터 흐름으로 알고리즘을 짜는 것이 편하다.
왜냐하면, 예제를 기준으로 누적해서 더한 것이 15가 되는지 체크를 해줘야 하기 때문이다.

정리하자면
•순서대로 누적합을 해서 N을 찾는 것이기 때문에 진행방향이 같은 투 포인터 알고리즘으로 진행하는 것이 편하다.

나머지는 코드로 알아보자.
코드는 총 2개의 버전이 있다.
첫번째 버전은 배열을 쓰지 않은 풀이이고, 두번째 버전은 배열을 사용한 풀이이다.

import java.io.*;

public class BOJ_2018_5 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2018
		
        //입력을 빨리 받기 위해서 BufferedReader 클래스 객체를 선언해준다.
        //여러 숫자들을 한 줄에 여러개를 받으면 숫자들을 파싱할 필요가 있지만,
        //이번엔 입력을 한 줄에 한번만 받기 때문에 StringTokenizer 클래스 객체는 선언하지 않는다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //한 줄에 숫자 하나를 입력받은 것을 int형으로 형변환시켜주고 N에 저장한다.
		int N = Integer.parseInt(br.readLine());
		
        //start는 시작 숫자, end는 끝 숫자, sum은 start와 end를 더한 값, 
        //answer는 더해서 N이 되는 개수에 대한 변수다.
		int start = 1, end = 1, sum = 1, answer = 1;
		
        //투 포인터 알고리즘
        //start < N을 조건으로 달은 이유는 while문은 반복문 내용이 진행되다가 조건에 어긋나면
        //바로 반복문이 종료되는 것이 아니기 때문에 start <= N 조건으로 하지 않았다.
		while(start < N) {
        	//start 숫자와 end 숫자를 더한 값이 N과 같으면
            //answer를 늘려주고 start를 제거해준다.
            //왜냐하면 이미 현재 시작항을 포함한 end값까지 더한 경우를 answer에 추가했기 때문이다.
            //따라서 제거해준 다음, start를 하나 늘려서 다음 케이스를 찾는다.
			if(sum == N) {
				++answer;
				sum -= start;
				++start;
			} else if(sum < N) {
            	//sum이 N보다 작다면 sum을 늘려줘야 하므로 end를 늘려줘야 한다.
                //늘려준 다음, sum에 end를 더해준다.
				++end;
				sum += end;
			} else {
            	//그 밖의 케이스라면 sum > N인데, 이 경우에는 숫자를 줄여줘야 하기 때문에
                //start를 sum에서 제거해주고
                //start를 1씩 늘려준다.
				sum -= start;
				++start;
			}
		}
		
        //그렇게 구해진 답을 출력해준다.
		System.out.println(answer);
	}
}

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

public class BOJ_2018_3 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2018번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int[] nums = new int[N+1];
		
        //배열 각 칸마다 숫자를 순서대로 저장해준다.
		for(int i=0; i<=N; i++) {
			nums[i] = i;
		}
		
        //sum이 nums[0]인 이유는 sum이 0이게 되면 배열의 첫 항이 
        //누적합에 들어가지 못하기 때문이다.
		int start = 0, end = 0;
		int sum = nums[0];
		int answer = 1;
		
        //투 포인터 알고리즘
		while(end <= N-1) {
			if(sum == N) {
				++answer;
				++end;
				sum += nums[end];
			} else if(sum < N) {
				++end;
				sum += nums[end];
			} else if(sum > N) {
				sum -= nums[start];
				++start;
			}
		}
		
		System.out.println(answer);
	}
}

이 때 두번째 코드보단 첫번째 코드가 메모리도 덜 잡아먹으며 속도도 좀 더 빠르기 때문에,
책에서는 첫번째 버전을 채택한게 아닐까 싶다.

문제: https://www.acmicpc.net/problem/2467

투 포인터에 대해서 공부한다고 했을 때 알고리즘 단톡방에 계신 분께서 추천해주신 문제다.
필자는 이 문제로 두개의 포인터가 같은 방향으로 이동하는 것과 서로 다른 방향에서 진행되는 알고리즘의 차이를 알 수 있었다.
당연한 얘기지만 이 문제를 풀 때 정말 머리를 쥐어 싸맸던 것으로 기억한다.
이제 따끈따끈하게 실버가 된 뉴비에게 골드 문제는 아직까지도 많이 어려웠다.
하지만 나도 할 수 있었던 만큼 다른 분들도 투 포인터 알고리즘을 알고만 있다면 할 수 있을 것이라고 생각한다.
지금부터 문제 분석부터 차근차근 넘어가보자.

일단 문제에서 요구하는 것 자체는 그리 어렵지 않다.
두 용액의 합이 최대한 0과 가까우면 되는 문제이다. 출력은 그 두 용액을 출력하면 된다.
하지만 여기서 문제점이 생긴다. 더해서 0과 가장 가까운 값을 찾으려면 어떻게 해야 하지?
즉, 우린 여기서 투 포인터 + 근사값 알고리즘 이렇게 같이 알아야 이 문제를 풀 수 있다.
물론 이분탐색으로도 풀 수 있지만, 일단 이 글에선 투 포인터로 주제를 잡고 풀겠다.

0과 근사한 값을 구하려면 어떻게 해야 할까?
일단 0에서 얼마나 떨어져있는지를 체크하고, 이 값과 비교할 이전의 최소 거리값이 있어야 할 것이다.
그러기 위해선 우린 절대값을 사용해야 한다. 왜냐하면 절대값 자체가 수직선의 거리를 뜻하기 때문이다.
그리고 더해서 나온 최소값이 이전의 최소 거리값보다 작다면 최소값을 바꿔주고 더해지는 값들을 답으로 지정하면 된다.
그리고 우린 그 더해지는 값들을 투 포인터로 찾으면 된다. 말로 하면 어렵지만, 그림으로 보면 쉬울 것이다.

정리하자면
① 서로 더해지는 숫자들은 투 포인터 알고리즘을 이용해서 바꿔준다. (0을 기준으로)
② 더한 값이 0이랑 가까운지 체크하는건 근사값 알고리즘을 사용한다.

그럼 이제 코드를 살펴보자.

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

public class BOJ_2467_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 2467
		
        //입력을 빨리 받기 위한 BufferedReader 클래스와 숫자들을 파싱할 STringTokenizer 클래스 객체
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //용액의 개수
		int[] nums = new int[N]; //용액 개수만큼의 배열 선언
		
        //st 변수 초기화. BufferedReader 클래스는 한 줄씩만 읽어오기 때문에,
        //입력받는 줄이 달라진다면 st를 초기화해줘야 한다.
		st = new StringTokenizer(br.readLine());
        
        //용액의 숫자들을 입력받는 반복문
		for(int i=0; i<N; i++) { 
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //start는 배열의 시작 인덱스, end는 배열의 끝 인덱스,
        //asnwer1, answer2는 0과 더해서 0과 가장 가까운 2개의 용액 값을 저장할 변수들이다.
        //min은 이전 최소값이다. 하지만 지금은 비교 대상이 없기 때문에(아직 반복문에 들어가지 않음) 
        //Long의 최대값으로 저장해놓은 상태다.
		int start = 0, end = N-1, answer1 = 0, answer2 = 0;
		long min = Long.MAX_VALUE;
		
        //투 포인터 알고리즘 + 근사값 알고리즘
		while(start < end) {
        	//더한 값은 반복이 돌 때마다 변해야 하므로 반복문 안에서 선언하고 값을 더해준다.
            //abs는 더한 값의 절대값이다.
            //따로 저장하는 이유는 sum 값의 범위에 따라서 
            //start를 증가 시키거나 end를 감소시켜야 하기 때문이다.
			long sum = nums[start] + nums[end];
			long abs = Math.abs(sum);
			
            //만약에 이전 합이 현재 더한 것보다 크다면 - 새로운 최소값 탄생
            //min의 값을 바꿔주고 answer1, 2에다가 현재 용액의 값들을 저장해준다.
            //저장해주고 만약 sum이 0이라면 이미 0과 가장 가까운 용액의 값을 찾은 것이므로
            //반복문을 종료시켜준다.
			if(abs < min) {
				min = abs;
				answer1 = nums[start];
				answer2 = nums[end];
				
				if(sum == 0) {
					break;
				}
			}
			
            //만약에 sum이 0보다 작다면 - 0과 가장 가까운 값이 되어야 하므로
            //0보다 작은 값이 나온다면 start 인덱스를 증가시켜주고,
            //반대의 경우엔 end를 줄여준다.
			if(sum < 0) {
				++start;
			} else {
				--end;
			}
		}
		
        //반복문이 종료된다면 두 용액들을 출력해준다.
		System.out.println(answer1+" "+answer2);
	}
}

문제: https://www.acmicpc.net/problem/10986

책에 나오는 구간합 문제의 끝판왕.. 역시나 문제 분석하기 파트에 나오는 식들이랑 말은 이해가 되지 않았고..
그렇게.. 삽질이 2~3일간 계속 지속됐다. 책에서는 실버 4의 난이도라고 되어있지만, 현재는 골드 3의 난이도다.
솔직히 필자는 실버문제들을 푸는데도 너무 오래 걸리고 이해하는 데에도 너무 어려웠는데 골드 난이도라니!
그래도 이왕 여기까지 온 거 이 문제를 대충 넘어갈 수 없었기에 이것도 분석을 해보았다.
문제 이름이 나머지 합 구하기라고 해서 진짜 나머지들을 구한 것들을 더하는 것이 아니라,
연속되는 숫자를 더한 값의 나머지가 0이 되는 순서쌍의 개수를 구해야 한다.
즉, 경우의 수의 개념 중의 하나인 조합이 들어간다는 것이다. 참고로 필자는 경우의 수나 조합 문제를 어떻게 풀었냐면,
경우의 수 같은 경우에는 일일이 노가다해서 풀었으며, 조합은 공식과 문제 형식을 단순암기해서 풀었다.
덕분에 시험지와 교과서는 노가다의 흔적으로 그 파트만 빽빽해지고 너덜너덜해졌던 기억이 난다.
하지만 걱정할 필요 없다! 지금이라도 조합에 대해서 제대로 알고 풀면 된다.
사실 필자도 이 문제 때문에 조합을 다시 공부했다.
조합이란, 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서 상관없이 r개의 원소를 고르는 것이다.
위키백과에선 이렇게 설명하고 있어서 복잡해보일 수도 있지만, 예를 들어보자.
주머니에 10개의 구슬이 있다. 구슬들에는 번호도 없고. 색깔도 모두 같다. 그 중에 2개를 뽑는다고 가정하자.
그럼 그 구슬을 꺼내는데에 순서가 필요한가? 결과적으로 우리는 그 중에 2개의 구슬을 뽑은게 되는 것이다.
이렇게 뽑는 순서가 중요하지 않고, 결과적으로 먼저 뽑은 것을 제외한 나머지를 뽑게 된다면 조합을 사용하고,
순열은 뽑는 순서가 정해져있으며, 뽑은 것을 나열해야 한다면 사용하는 것이다.
순열의 기호는 \(_{n}P_{r}\)이고, 조합의 기호는 \(_{n}C_{r}\)이다. 이때, \(_{n}C_{r}\)은
$$\frac{n(n-1)(n-2)...\{n-(r-1)\}}{r!}$$

이때, 분자에 위치한 n은 r개 만큼 곱하는 것이다. 예를들어 10개 중에 2개를 뽑는다고 했을 때, 처음엔 10개중에 하나니까 10가지의 경우의 수가 있지만, 하나를 뽑고 나서는 9개의 경우의 수가 있기 때문에 10*9를 해준다. 여기서 2개만 하는 이유는 우리는 구슬을 2개만 뽑는 것이기 때문이다. 3개를 뽑는다면 8가지의 가능성이 또 생기기 때문에 10*9*8을 해줘야 한다. r!을 나누는 이유는 뽑은 순서는 다르지만 같은 구슬을 뽑았을 경우를 없애주기 위해서이다.
이제 문제를 풀기 위한 수학적 개념은 다뤘으니, 이제 다시 문제로 넘어와보자.
사실 필자는 문제 분석하기 파트의 나머지 합 문제 풀이의 핵심 아이디어 부분을 또 이해하지 못했기 때문에,
'이게 무슨 말이지' 하면서 분석했었다.
아래는 책에 적혀있는 핵심 아이디어 부분을 내 스타일대로 고쳐써본 것이다.

1. (A+B)%C = ((A%C) + (B%C))%C, 고로 (A+B)%C로만 계산해도 된다.
2. 합 배열 S[(현재항)] - S[(전 항)]은 원본 배열의 (전 항)+1 ~ (현재항)까지의 구간 합이다.
3. 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[(현재항)]과 S[(전 항)]이 같다면 원본 배열에서
   (전 항)+1 ~ (현재항)까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.
   (S[(현재항)]%M = S[(전 항)]%M 이면 (S[(현재항)] - S[(전 항)])%M = 0)

자, 이제 문제에 대한 분석은 끝났다. 코드로 넘어와보자.
합 배열 S에 누적합의 값을 저장해준다. 누적합의 자세한 설명은 https://life-study-1031.tistory.com/7

이 글에 자세히 있으니 누적합에 대해서 잘 모르겠다면 이 글을 참고해주면 된다.
누적합의 값을 저장하는 이유는 합이 M으로 나누어떨어지는 순서쌍을 구해야 하기 때문이다. 누적합을 구한 다음, M으로 나눠서 나누어떨어진다면 1항부터 그 항(n항이라고 가정하자)까지 더한 값이 나누어떨어지는 것이기 때문에 (1,n)이 성립되므로, 답이 될 수 있는 것이다.
그 다음으로는 조합의 개념을 이용하여 답을 구해야 되는데, 그러기 위해선 먼저 나머지의 개수를 셀 수 있어야 한다. 예를 들어보자. 나머지가 [1, 0, 0, 1, 0]일 경우, 0이 3개가 있다. 이때 0이 나오는 순서쌍은 각각 다를 것이다. 그렇게 0이 나오는 3가지 경우 중에서 i와 j에 해당하는 순서쌍을 순서와 상관없이 뽑는 것이기 때문에 \(_{3}C_{2}\)를 해야 하고, 그것을 위해서는 나머지의 개수가 필요하다. 물론 0하나에 i,j 순서쌍이 있기에 \(_{6}C_{2}\)가 아닌가요? 생각할 수도 있겠지만, 이렇게 되면 나머지가 0과 달라지는 순서쌍이 나올 수도 있기 때문에 \(_{3}C_{2}\)를 해야 한다.
여기서 질문이 나올 수 있다. 나머지가 0인 것들의 경우만 세면 되는데, 왜 굳이 0보다 큰 나머지들의 개수도 세는 것인가? 이는 문제를 분석할 때 3번에 해당하는 개념을 이용한건데, S[(현재항)]과 S[(전 항)]의 값이 같으면 (전 항)+1 ~ (현재항)까지의 구간 합이 M으로 나누어떨어지는 구간이기 때문에 0보다 큰 나머지의 개수도 세어주는 것이다.
구글링으로 찾은 풀이와 책에서 나온 풀이들의 공통점을 찾자면 S[i]%M의 값과 나머지를 저장하는 배열의 인덱스가 같다는 것인데, 이렇게 설정한 이유는 그 나머지의 개수를 구하기 위해서이다. 예를 들어, 나머지가 [1, 0, 0, 1, 0] 이렇게 나왔다면 사람은 0이 3개, 1이 2개 이렇게 셀 수 있지만 컴퓨터는 일일이 1씩 더해줘야 하기 때문에, 나머지를 저장하는 배열의 인덱스와 같게 한 것이다. 그림을 보면 이해가 쉬울 것이다.

이런 식으로 저장이 되는 것이다. 우린 이제 \(_{3}C_{2}+_{2}C_{2}\)의 값을 구하면 된다.

이제 풀이에 관련된 코드파트도 끝이 났다.

이번에는 수학의 개념과 코딩이 같이 나와서 필자도 이 글을 쓰는데에 3~4일 정도 걸린 것 같다.
내용이 정리가 잘 되지 않았기 때문이다. 이제는 작성하면서 많이 정리가 돼서 머릿속이 한결 깔끔해진 것 같다.
이번 내용을 요약하자면
① 이 문제를 풀기 위해선 수학적 개념 중 조합을 사용해야 한다.
    조합의 수식은 \(\frac{n(n-1)(n-2)...\{n-(r-1)\}}{r!}\)
② 나머지를 저장하는 배열의 인덱스 = 나머지 이렇게 연산을 해서 나머지의 개수를 세어준다.
    그 이유는 순서쌍의 경우의 수를 더해주기 위해서.
첫번째로 합배열 S에 나머지를 그대로 넣어서 계산하는 코드다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO 백준 10986번
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 이용해서 입력을 받음
        //BufferedReader 클래스로 입력을 받으면 문자열 파싱이 필요함.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N = 숫자를 입력받을 개수, M = 입력받을 숫자들을 나눌 숫자
        //sums = 합배열 S, count = 나머지 배열, answer = 순서쌍 개수
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		long[] sums = new long[N+1];
		long[] count = new long[1000];
		long answer = 0;
		
        //누적합 배열 만들기
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
		}
		
		for(int i=1; i<=N; i++) {
			//sums[i]에 %M 연산을 하고 sums[i]에 다시 저장
            sums[i] %= M;
			
            //나머지가 0이면 answer를 더해줌 = 순서쌍의 개수를 세어줌
			if(sums[i] == 0) {
				++answer;
			}
			
            //나머지에 해당하는 인덱스에 1을 더해줌
			++count[(int)sums[i]];
		}
		
        //조합을 이용한 수식
        //2를 나눈 이유는 2! = 1*2 = 2 이기 때문이다.
		for(int i=0; i<count.length; i++) {
			if(count[i] > 1) {
				answer += count[i]*(count[i]-1)/2;
			}
		}
		
        //정답 출력
		System.out.println(answer);
	}

}

두번째로는 새로운 변수를 이용한 방법이다.

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

public class BOJ_10986 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 10986
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); //입력받을 숫자의 개수
		int M = Integer.parseInt(st.nextToken()); //나눌 수
		long[] sums = new long[N+1];
		long[] count = new long[1000];
		long answer = 0;
		
        //이렇게 하면 for문을 1개만 써도 합배열 S의 값을 손상시키지 않고 계산하는 것이 가능하다.
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
            //나머지를 저장하는 변수를 선언함.
			int rem = (int) (sums[i]%M);
			
            //나머지가 0이면 answer를 늘려준다.
			if(rem == 0) {
				++answer;
			}
			
            //나머지를 나머지 배열의 인덱스로 이용하여 나머지의 개수를 세어준다.
			++count[rem];
		}
		
		for(int i=0; i<count.length; i++) {
			if(count[i] > 1) {
				answer += count[i]*(count[i]-1)/2;
			}
		}
		
		System.out.println(answer);
	}
}

문제: https://www.acmicpc.net/problem/11660

이 문제를 보기 전까지는 구간합도 할 만하다고 생각하다가 딱 이 문제를 보는 순간,
와.. 내가 이걸 풀 수 있을까 이 생각이 들었다. 나한테는 이 문제가 거의 최종 보스처럼 느껴졌다.
왜냐하면 필자는 2차원 배열에 울렁증이 있기 때문이다. 전 직장에서도 배열을 다루는 게 능숙지 않아 보인다는 말을 여러 번 들었을 정도로 초보중의 초보였다. 그런데 이런 문제를 분석해서 푼다? 정말 가능성이 단 1도 없어 보였다.
하지만 이 역시 분석하지 않고 넘어가게 되면 결국엔 다른 직장에 가서도 똑같은 소리를 듣게 될 게 뻔하고,
결국 공부다운 공부를 못한 것이 되어버린다. 그래서 이 문제도 하나하나 분석을 해나갔다.
결과적으로는 분석을 해냈고, 2차원 배열의 거부감도 조금은 덜게 되었다.

서론이 좀 길었는데, 먼저 2차원 배열에 대해서 알아보자.
2차원 배열이란, 말 그대로 1차원 배열이 여러 개로 이루어져 있어, 면 형태를 띠고 있다고 보면 된다.

따라서 이 2차원 배열을 다루기 위해선 2중 반복문이 거의 필수적으로 나온다.
책에서는 구간합 알고리즘을 기준으로 알려주기 때문에,
구간합 알고리즘을 이용한 문제풀이 방식을 분석한 것이다.
필자가 구글링으로 알아본 결과, 이 문제에서는 DP(Dynamic Programing)보다 구간합 알고리즘이 속도가 빠르다고 하여 구간합에 집중할 수 있었다. DP에 대해서는 아직 공부를 못했기 때문에, 차후에 글을 작성해볼 생각이다.

생각하기 쉽게 예제를 통해 생각을 해보자.
처음에 4를 입력해서 4칸x4칸 = 16칸의 2차원 배열이 만들어졌다.
그러면서 값을 순서대로 넣기 시작한다. 그럼 이렇게 그림이 그려진다.

우린 여기서 구간합을 구해야 하기 때문에 결국 누적합을 구해야 한다.
근데 어떻게 구해야 위, 아래로 더해지는 것도 대비를 할 수 있을까?

책에서 나온 공식이 있지만, 역시나 필자는 한 번에 이해를 하지 못했기 때문에 하나씩 분석을 해봤다.
누적 합의 배열도 역시나 2차원 배열일 수밖에 없다. 왜냐하면 숫자를 입력받은 배열 자체가 2차원이기 때문이다.

일단 일차원 누적합은 간단했다. S[i] = S[i-1] + N[i]. 근데, 이 문제는 좀 더 복잡하다.
우리가 만들 누적 합의 값을 적어보자면 위와 같은 식이다. 따라서 우리는 N[i][j]도 더해줘야 하는 것이다.
이유는 https://life-study-1031.tistory.com/7 여기에서 잘 설명되어있으니 참고 바란다.

돌아와서, 일차원의 누적합을 저장할 때는 S[i] = S[i-1] + N[i] 이 형태로 했었는데,
이건 2차원 배열임을 다시 한번 상기시키면서 생각해보자,
S[i-1]을 더하는 이유는 결국 그 항이 이번 항 그 전까지의 누적합이기 때문에 더하는 것이다.
그럼 2차원에서는 어떻게 해야 그 전항까지의 값을 더할 수 있을까?
바로 가로줄과 세로줄을 하나씩 줄인 값을 더하는 것이다.

여기서 우리가 알아야 할 것은, 이차원 배열을 다룰 때 A[i][j] 이런 형태로 다루게 되는데,
이 원리를 잘 알아야 한다는 것이다. 단도직입적으로 말하면 A[(가로줄)][(세로줄)]이다.
이걸 그림으로 설명해보자면 아래와 같다.

그렇게 되면 만약에 S(i,j) = S(2,3)의 누적합을 구해야 한다고 했을 때, S(1,3)은 결국 N(1,1)~N(1,3)까지 더한 값이며, S(2,2)는 N(1,1)+N(1,2)+N(2,1)+N(2,2)를 다 더한 값이기 때문에 1차원 배열에서 했던 현재항 이전의 항을 더하는 것과 동일한 수순이 되는 것이다.

그런데 이렇게 한 줄씩 줄인 것을 더하게 되면 문제가 생긴다. 그럼 2번 더해지는 부분이 생길 텐데, 그 부분은 빼줘야 하지 않은가? 그래서 현재 항의 대각선에 있는 항은 빼준다. 예를 들어 S(2,3)을 구한다고 해보면, N(1,1), N(1,2)는 중복으로 더해진다. 따라서 이런 부분을 빼주기 위해 대각선에 있는 항을 빼주는 것이다.

그럼 이제 남은 건 하나다.
예제에서 나오는 S(2,2) ~ S(3,4)까지의 합을 어떻게 구할 것이냐?

이것도 그림으로 보면 편하다.

갈색으로 칠한 부분이 N(1,1) ~ N(3,4)까지 모두 더한 값이고, 분홍색은 거기에서 N(1,1) ~ N(1,4)까지 더한 값이다.
그리고 보라색은 N(1,1) ~ N(3,1)까지 더한 값이다.
즉, 우리는 저 값들을 빼야 N(2,2) ~ N(3,4)까지의 값을 더할 수 있다.
다만 그러면 두 번 빼게 되는 값이 있다. 바로 N(1,1), N(1,2)이다. 따라서 처음에 입력받는 x,y 값에서 1씩 빼주면 두 번 빼게 되는 값을 가리킬 수 있고, 그걸 더해주면 되는 것이다.

여기까지 오느라 정말 머리가 터질 것 같은 기분 너무 잘 안다. 이제 진짜 다 왔다.
우리는 이걸로 2가지를 도출할 수 있다.
① 2차원 배열에서 구간합을 구하는 식:
     S[(가로줄)][(세로줄)] = S[(가로줄)-1][(세로줄)] + S[(가로줄)][(세로줄)-1] - S[(가로줄)-1][(세로줄)-1]
② 질의에 대한 답을 구할 수 있는 식(x1, y1은 처음에 입력받는 좌표, x2, y2는 두 번째로 입력받는 좌표): 
     S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

이걸 코딩으로 표현하자면 아래와 같다.

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

public class BOJ_11660 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 11660
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 사용함.
        //입력받은 문자열을 파싱하기 위해 StringTokenizer 클래스를 사용함.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] nums = new int[N+1][N+1];
		long[][] sums = new long[N+1][N+1];

		//숫자 입력받고 합 구하기
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				nums[i][j] = Integer.parseInt(st.nextToken());
				sums[i][j] += sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + nums[i][j];
			}
		}
		
		//답 구하기
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			System.out.println(sums[x2][y2] - sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1]);
		}
	}
}

문제: https://www.acmicpc.net/problem/11659

필자는 처음에 이 문제를 풀기 전에, 구간 합의 핵심 이론 부분의 합 배열 S를 만드는 공식이 이해가 되지 않았다. 
그래서 그냥 따라 치고 넘겼었는데, 이런 습관은 좋지 않은 습관이라고 피드백받아,
하나하나 분석하면서 다시 풀고 또 풀고 그랬었다. 그렇게 2번 정도 풀었을 때는 그 공식과 유사한 코드를 짰으며,
3번째에는 공식과 같은 코드를 짰다. 사실 공식이라기 보단 그냥 누적합 배열을 만드는 것이니까 공식의 형태로
적혀있는 것이다. 이게 무슨 말인지는 하나하나 분석을 하면 알 수 있다. 지금부터 그걸 알아보자.

우선 누적합이란 단어에 대해서 생각을 해봐야 한다.
예를 들어, 숫자가 [1, 2, 3, 4, 5]가 있으면 누적합은 [1, 1+2, 1+2+3,... , 1+2+3+4+5]
이런 식으로 하나씩 더해가는 합의 형태이다.

즉, 항이 하나씩 늘어날 때마다, 해당하는 항에 있는 숫자를 더하면 되는 것이다.

그러면 책에서 설명한 합 배열 공식의 원리를 우리는 지금 이해를 한 것이다.
합 배열을 S, 숫자 배열을 N이라고 둔다면, S[(현재 항)] = S[(이전 항)] + N[(현재항)] 이렇게 되는 것이다.

이 내용을 기억하고 문제를 봐보자.
문제에서 요구하는 것은 입력받는 첫번째 값부터 두 번째 값까지의 값을 요구하고 있다.
예제에 나온 것으로 예를 들자면, [5,4,3,2,1]의 누적합은 [5, 9, 12, 14, 15]이다.
여기에서 1항~3항까지의 합을 구한다고 생각을 해보면, 12가 그 답이 될 수 있을 것이다. 왜냐하면 1~3항을 누적해서 더한 게 12이기 때문이다.
그럼 2항~4항까지의 합을 구한다면 어떻게 해야 할까? 2번째 항에서 4번째 항까지 더한다고 하면 일단 1항~4번째 항까지 더한 것에서 1항의 값을 빼면 되므로, 14-5 = 9 이렇게 되는 것이다.
5항 ~ 5항까지의 합을 구한다면 마찬가지로 1번째 항에서 5번째 항까지 더한 것에서 4번째 항까지 더한 것을 빼면 되므로, 15-14=1 이렇게 되는 것이다.

그럼 문제가 생긴다.
첫 번째 항부터 더한 것과 최소 두 번째 항부터 더한 것을 구별을 해야 한다.
이 문제를 해결하기 위해서 책에서 소개하는 누적 합의 알고리즘은 [0, 5, 9, 12, 14, 15] 이렇게 되어있다.
즉, 1항~3항까지의 합을 구할 때에는 1항~3항까지 더한 값인 12에서 0을 빼는 것이다. 그럼 12일 테니까.

그럼 우리는 두 개의 패턴을 알아낼 수 있다.
첫 번째로 입력받는 항을 i라고 하고, 두 번째로 입력받는 항을 j라고 하자.
① S[(현재 항)] = S[(이전 항)] + N[(현재항)] = S[(현재항)] = S[(현재항 - 1)] + N[(현재항)]
② S[j] - S[i-1]

이전항이 왜 현재항 - 1이냐면, 이걸 인덱스로 생각했을 때,
예를 들어 2가 현재 항이라 가정하면, S[2] = S[1] + N[2] 이런 형식이기 때문이다.

그럼 이제 코드를 살펴보자.

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

public class BOJ_11659 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 11659
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 이용함.
        //BufferedReader 클래스는 한 줄 단위로 입력을 받기 때문에
        //StringTokenizer 클래스로 문자열을 파싱해줘야 함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N = 항의 개수
        //M = 문제에서 요구한 것들이 몇 개인지(질의가 몇 개인지)
        //sums = 누적합을 저장할 배열 변수
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken()); 
		long[] sums = new long[N+1];
		
        //누적합을 구하는 반복문
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
		}
		
        //질의에서 요구하는 항들을 입력받고
        //합을 출력함
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int index1 = Integer.parseInt(st.nextToken());
			int index2 = Integer.parseInt(st.nextToken());
			
			System.out.println(sums[index2] - sums[index1-1]);
		}
	}
}

문제: https://www.acmicpc.net/problem/1546

이 문제는 처음에 봤을 때 이해가 되지 않는 문제였다.

필자는 책에 있는 문제 분석하기 파트를 읽어도 헤맸는데,
그 이유가 점수를 계산하는 방식에서 점수/최댓값*100을 하면 0아닌가???
이러면서 예제 출력을 이해하지 못했었다.
근데 알고리즘 단톡방에 계신 분들 중 double형으로 생각해보라고 조언해주신 분 덕분에 한번에 이해가 되었다.

문제에서 예시를 든 수학점수를 계산하는 것은 50/70*100인데, 이걸 int형으로 계산해보면 0으로 나올 것이다.
하지만, double 형으로 바꾸면 71.43으로 결과가 나오는 것을 보면,
이 값은 0.7143xxx 이런 식으로 나오는 것을 알 수 있다.

그리고 평균을 구하는 식은 각 (과목의 점수들의 합/과목수) 이건데,
여기에선 각 과목의 점수들(원점수)을 각각 A,B,C라고 보고, 가장 높은 점수를 max라 생각해보자.

이런식으로 계산이 되는데, 부끄럽지만 필자는 엄청난 수포자였기 때문에 책에 있는 (A+B+C)*100/max/3 이게 한눈에 안들어와서 직접 해체했던 기억이 있다. 필자는 (A+B+C)*100/3*max 이렇게 되는거 아닌가 생각을 했었는데,
괄호를 (A+B+C)*100/(3*max) 이렇게 하면 맞는걸 확인할 수 있다.

자 그럼 이제 코딩으로 넘어와보자. 코딩으로는 2개의 문제가 있다.
① 최대값 구하기 - Arrays 클래스에 있는 sort 함수를 써도 되고, for문으로 찾아도 된다.
② 배열에 변수를 저장하고 합을 구하기

1번 같은 경우에는 2가지의 해결방법이 있는데, sort버전과 for문 버전의 결과와 코딩은 밑에서 확인할 수 있다.
2번 같은 경우에는 입력받는 것을 점수를 저장하는 배열에 넣으면 되는데 Scanner를 이용한다면 scores[i] = sc.nextInt(); 로 쓸 수 있겠다.

따라서 코드를 살펴보자면,

//버전 1. for문 사용해서 최대값 찾기

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

public class BOJ_1546 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 1546
		
        //입력을 빨리 받기 위해서 BufferedReader 클래스를 사용해준다.
        //BufferedReader 클래스로 이용한 입력은 한 줄 단위로 읽기 때문에 문자열 파싱이 필요함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N은 과목 수, sum은 점수의 총합(가공x), max는 점수의 최대값을 저장할 변수이다.
        //scores 배열은 점수들을 저장할 배열이다.
		int N = Integer.parseInt(st.nextToken());
		int sum = 0, max = 0;
		int[] scores = new int[N];
		
        //점수 배열에 입력받은 점수들을 저장해주고,
        //그 점수들을 다 더해준다.
        //만약에 max변수가 scores[i] 보다 작으면 max에 scores[i]를 저장해준다.
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) { 
			scores[i] = Integer.parseInt(st.nextToken());
			sum += scores[i];
			if(max < scores[i]) {
				max = scores[i];
			}
		}
		
        //평균 출력
		System.out.println((double)sum*100/max/N);
	}
}

2번째 코드.

//버전 2. Arrays.sort()를 사용한 코드

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

public class BOJ_1546_ver2 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 1546
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int sum = 0, max = 0;
		int[] scores = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			scores[i] = Integer.parseInt(st.nextToken());
			sum += scores[i];
		}
		
        //배열을 오름차순으로 정렬해주고 최대값을 저장해준다.
		Arrays.sort(scores);
		max = scores[N-1];
		
        //저장된 최대값을 출력한다.
		System.out.println((double)sum*100/max/N);
	}
}

sort로 한 것과 for문으로 한 것의 메모리 차이와 시간

어? if문이 줄었는데, 왜 sort가 더 메모리와 시간을 더 잡아먹지? 에 대해서 궁금할 수 있다.
이건 필자가 JAVA_travel에서 차후에 다룰 내용이긴 한데,
sort는 왜 메모리를 좀 더 잡아먹을까? 에 대한 탐구를 할 예정이다.

문제: https://www.acmicpc.net/problem/11720

퇴사할 때 즈음 구매해놨던 알고리즘 책이 있다.
http://www.yes24.com/Product/Goods/108571508

이 책인데, 여기에서 나오는 자료구조 파트의 첫번째 문제가 바로 지금 문제다.

처음에는 이 문제를 엄청 단순하게 생각해서 BufferedReader를 이용해서 입력을 받은 다음, StringTokenizer 클래스로 숫자들을 파싱할 생각이었는데.. 보니까 공백없이 입력을 받는 것이어서 적잖이 당황했던 기억이 있다.

그래서 책에서도 찾아보고, 구글링도 해본 결과, 이 문제는 char 자료형 배열로 저장해서 해결해야 하는 문제였다.
즉, ASCII(아스키)코드를 이용해서 풀어야 하는 문제인 것이다.

ASCII코드란, 문자 인코딩 숫자이다. 엇? 인코딩? 인코딩이란 단어에 복잡함을 느낄 필요는 없다.
인코딩은 문자나 기호들을 컴퓨터가 인식할 수 있도록 변환한 것이기 때문이다.
https://ko.wikipedia.org/wiki/ASCII

백준의 문제를 풀기 위해 필요한 부분은 위키백과의 <출력가능 아스키 코드표> 부분이다.
보면 숫자 0은 ASCII 코드로 15이며, 1,2,3 ... 이렇게 갈 수록 아스키코드가 1씩 늘어난다는 것을 알 수 있다.

즉, 예제 입력중 54321을 입력을 받으면, 이건 String 형태로 입력을 받고, char 배열에 반복문으로 char[0] = 5, char[1] = 4 ... 이런 식으로 넣어준 다음, 그 합을 저장하는 sum이라는 변수를 만들어서 sum += char[i]-'0' 으로 하면 15가 빠지기 때문에 1은 16-15 = 1이 되고, 2는 17-15 = 2 이런식으로 계산할 수 있다. 그림으로 표현하자면,

이걸 코드로 표현을 해보자면,

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

public class BOJ_11720 {

	public static void main(String[] args) throws IOException{
		//TODO 백준 11720
		
        //입력을 빠르게 받기 위해 BufferedReader 클래스와 
        //입력받은 문자열을 파싱하기 위해 StringTokenizer클래스를 이용해준다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N은 숫자의 개수, nums_string은 입력받는 숫자들을 저장할 변수이다.
        //nums_char는 입력받은 숫자들을 char형으로 저장할 변수이다.
        //sum은 그 배열에 있는 값들을 모두 더해줄 변수이다.
		int N = Integer.parseInt(st.nextToken());
		String nums_string = br.readLine();
		char[] nums_char = new char[N];
		int sum = 0;
		
        //String은 문자"열"이기 때문에 그 길이를 사용할 수 있다. (문자열 = 문자들로 이루어진 배열)
        //.charAt()은 해당 인덱스에 해당하는 문자를 char로 변환해주는 메소드이다.
		for(int i=0; i<nums_string.length(); i++) {
			nums_char[i] = nums_string.charAt(i);
			sum += nums_char[i]-'0';
		}
		
        //char 배열에 있는 값들을 모두 더한 sum을 출력해준다.
		System.out.println(sum);
	}
}

BufferedReader와 Scanner의 차이는 나중에 JAVA_travel 카테고리에 자세히 작성할 것이지만,
간단하게 말하면 Scanner 클래스보다 BufferedReader 클래스를 이용해서 입력을 받는게 훨씬 빠르다.
그리고 입력을 받는게 있으면 당연히 출력하는 것도 있을건데, 그 클래스가 바로 BufferedWriter 라는 클래스다.
이것도 System.out.println() 보다 빠른데, 이것도 JAVA_travel 카테고리에 작성할 예정이다.