백준

2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 2차원 배열에서 누적합을 구하여라 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedRead..

14929번: 귀찮아 (SIB) n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다. www.acmicpc.net 문제 다음을 구하시오. 풀이 글로 작성하니 뭔가 규칙이 보였다. 규칙은 다음과 같다. N이 4인 경우 12, 13, 23은 이전의 3에 대한 합이고 나머지 1-4, 2-4, 3-4는 (1 + 2 + 3)*4이기 때문에 1~3까지의 합배열에 4를 곱한 것이었다. 처음에 풀었을 때이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt()+1; int[] O..

11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere..

1253번: 좋다 문제 주어진 수 배열에 대해서 배열의 값 X가 다른 배열의 두 값의 합으로 나타낼 수 있다면 “좋다”라고 표현한다. 주어진 배열에 대해서 좋은 수는 몇개인지 출력하시오. 풀이 주어진 값들을 정렬한다면 대상 값의 앞에 까지만 합을 계산해봐도 해당 값이 합으로 나타낼 수 있는지 알 수 있다. 따라서 먼저 수들을 정렬하고 배열의 첫번째 부터 대상 값의 바로 앞 까지의 값을 투포인터로 비교하면 된다. start값과 end값의 합을 구하고 대상 값보다 작다면 start값을 높이고 크다면 end 값을 낮춘다. 만약 대상 값과 같다면 다음 값을 대상으로 반복한다. 유의해야할 부분은 같은 값이 배열에 존재할 수 있다. import java.io.BufferedReader; import java.io...

2018번: 수들의 합 5 문제 주어진 수에 대해서 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하라. 풀이 주어진 수가 15일 때, 경우의 수는 다음과 같다. 1+2+3+4+5, 4+5+6, 7+8, 15 모든 수들은 자기 자신을 가지고 시작한다. 투포인터를 사용하면 쉽게 풀 수 있다. 두개의 포인터 i, j가 있을 때 i, j를 1부터 시작하여 두 점의 구간의 합을 구해나간다. 만약 구간의 합이 주어진 수 N보다 작다면 j를 높이고 주어진 수보다 크다면 i를 빼면서 올라간다. 만약 주어진 값과 같다면 i와 j 모두 움직인다. 즉, 다음과 같이 움직인다. 1 + 2 = 3 (3 < N) 1 + 2 + 3 = 6 (6 < N) 1 + 2 + 3 + 4 = 10 (10 < N) 1 + 2 + 3..

1940번: 주몽 문제 주어진 값들 중에서 2개를 뽑아서 더해 M값이 되는 경우의 수를 모두 구해라 풀이 배열을 정렬해서 작은 값과 큰 값을 움직이는 start와 end값을 이동시켜 해답을 찾아간다. 1.start와 end값의 합이 M보다 크다면 end값을 낮춘다. 2.start와 end값의 합이 M보다 작다면 start값을 높인다. 3.만약 M과 같다면 start와 end를 동시에 이동한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { publ..

10986번: 나머지 합 문제 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하시오. 풀이 이 문제는 나머지 연산은 묶어낼 수 있다는 점을 사용해야 한다. 합배열을 M으로 나눈 나머지 값을 계산한 배열을 계산한다. 여기서 나머지가 0이라는 의미는 주어진 배열 A[0] ~ A[i] 구간의 합이 M으로 나누어 떨어진다는 의미이다. 나머지 배열이 같은 값을 가지고 있다면 C[i] - C[j]는 0이 된다. 이 수식은 다음과 같이 볼 수 있다. 합 배열 S[i] - S[j]는 A[j] ~ A[i]구간의 합 배열이고 이 구간의 합 배열은 S[i] %M - S[j] % M = 0이 된다는 의미이다. 나머지 연산은 언제 계산하든지 상관 없기 때문에 나머지 연산 배열 C에서 같은 값을 꺼내 빼준다면 ..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 1차원 배열이 아닌 2차원 배열의 구간합을 구하는 문제이다. 풀이 단순히 2차원 배열로 확장한 것이 아니라 일정 4각형 범위의 구간합을 구하라는 문제이다. 다음과 같은 구간이 있다면 구간합 배열은 다음과 같다. 기존의 배열 A와 합배열 S가 있다면 다음과 같이 계산된다. S[x][y] = S[x-1][y] + S[x][y-1] + A[x][y] - S[x-1][y-1] 이를 그림으로 나타내보면 다음과 같다. S[2]..