본문 바로가기
백준

백준 닷컴 단계 별로 풀어보기 24단계

CD가참둥그렇다 2023. 11. 1. 10:13

1단계 구간 합 구하기 4 (백준 11659)

  • 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
  • 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
  • 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
import java.io.*;
import java.util.*;

public class Step_1 {
	static int n;
	static int m;
	static int[] arr;
	static int[] sums;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n + 1];
		sums = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sum+=arr[i];
			sums[i]=sum;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			sb.append(sum(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())) + "\\n");
		}
		System.out.println(sb.toString());
	}
	public static int sum(int from, int to) {
		return sums[to]-sums[from-1];
	}
}

A.

  • from~to까지의 누적합은 1~to까지의 누적 합 - 1~from-1의 누적 합과 같다는 성질을 이용한다.

2단계 수열 (백준 2559)

  • 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
  • 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.
  • 첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.
import java.io.*;
import java.util.*;

public class Step_2 {
	static int n;
	static int m;
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
		}
		int max = arr[m]-arr[0];
		int temp;
		for (int i = m+1; i <= n; i++) {
			temp = arr[i] - arr[i-m];
			if (max < temp) {
				max = temp;
			}
		}
		System.out.println(max);

	}
}

A.

  • from~to까지의 누적합은 1~to까지의 누적 합 - 1~from-1의 누적 합과 같다는 성질을 이용한다.

3단계 인간-컴퓨터 상호작용 (백준 16139)

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

public class Step_3 {
	static int m;
	static int[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		char[] s = br.readLine().toCharArray();
		arr = new int[s.length][26];
		int alp = s[0] - 97;
		arr[0][alp] = 1;
		for (int i = 1; i < s.length; i++) {
			alp = s[i] - 97;
			for (int j = 0; j < 26; j++) {
				if (j == alp) {
					arr[i][j] = arr[i - 1][j] + 1;
				} else {
					arr[i][j] = arr[i - 1][j];
				}
			}
		}
		int n = Integer.parseInt(br.readLine());
		int tempI, from, to;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			tempI = st.nextToken().charAt(0) - 97;
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			if (from == 0) {
				sb.append(arr[to][tempI] + "\\n");
			} else {
				sb.append(arr[to][tempI] - arr[from-1][tempI] + "\\n");
			}
		}
		System.out.println(sb.toString());

	}
}

A.

  • 입력 받은 문자열의 길이와 알파벳 26 만큼의 2차원 배열을 만들어준다.
  • 각 문자열의 문자마다 0~해당 위치까지 알파벳의 등장 회수를 세어준 2차원 배열을 완성한다.
  • 각 요청마다 to - (from-1)의 값을 반환하도록 한다.

4단계 나머지 합 (백준 10986)

  • 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
import java.util.*;
import java.io.*;

public class Step_4 {
    public static void main(String args[]) throws IOException {
        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 result = 0;           
        long[] S = new long[N + 1];      
        long[] count = new long[M];     
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            S[i] = (S[i - 1] + Integer.parseInt(st.nextToken())) % M;
            if(S[i] == 0) {
                result++;
            }
            count[(int) S[i]]++;
        }
        for(int i=0; i<M; i++) {
            if(count[i] > 1) {
                result += (count[i]* (count[i]-1) / 2);
            }
        }
        System.out.println(result);
    }
}

A.

  • 모든 경우의 수에 나머지를 구할 경우 시간초과가 발생한다.
  • 누적 합을 구하고 m으로 나눈 나머지로 저장한다.
  • 누적 합의 나머지가 0인 경우 즉시 result를 1 늘린다.
  • 나머지를 나머지를 세어줄 count배열에 넣어준다.
  • 나머지가 같은 경우 서로 빼 주었을 때 나머지가 0이 된다는 점을 이용한다.
  • 나머지가 같은 수 중 중복되지 않는 2 숫자를 고르는 경우의 수를 이용한다. n*(n-1)/2
  • 각 나머지에 대해 경우에 수를 산정하여 result에 더해준다.
  • result를 출력한다.

5단계 구간 합 구하기 5 (백준 11660)

  • N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
  • 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
  • 첫째 줄에 표의 크기 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.util.*;
import java.io.*;

public class Step_5 {
	public static void main(String args[]) throws IOException {
		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[][] sum = new long[n + 1][n + 1];
		long[][] box = new long[n + 1][n + 1];
		for (int i = 1; i < n + 1; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < n + 1; j++) {
				if (j == 1) {
					sum[i][j] = sum[i - 1][n] + Long.parseLong(st.nextToken());
				} else {
					sum[i][j] = sum[i][j - 1] + Long.parseLong(st.nextToken());
				}
				box[i][j] = box[i - 1][j] + sum[i][j] - sum[i-1][n];
			}
		}
		StringBuilder sb = new StringBuilder();
		int x1, x2, y1, y2;
		long temp;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			x1 = Integer.parseInt(st.nextToken())-1;
			y1 = Integer.parseInt(st.nextToken())-1;
			x2 = Integer.parseInt(st.nextToken());
			y2 = Integer.parseInt(st.nextToken());
			temp = box[x2][y2] - box[x1][y2] - box[x2][y1] + box[x1][y1];
			sb.append(temp + "\\n");
		}
		System.out.println(sb.toString());

	}
}

A.

  • 2차원 배열을 2개 만들어 준다. 하나는 누적 합을, 하나는 박스 합을 저장하는 배열이다.
  • 반복문을 만들고, 행 열의 숫자를 입력받으면 누적 합은 이전의 누적 합과 현재 값을 더한 결과를 대입하고, 박스 합은 x-1,y행렬의 박스 합과 현재 행렬의 누적 합을 더한 값에 x-1,n의 누적 합을 더한 결과를 대입한다.
  • 박스 합을 구해야 하는 구간을 받고, 각 구간에 대해 x2, y2의 값에서 x1-1, y2 / x2, y1-1의 박스 합을 빼고 x1-1, y1-1의 박스 합을 더한 결과가 해당 구간의 누적 합임을 이용하여 결과를 출력한다.

6단계 체스판 다시 칠하기 2 (백준 25682)

  • 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다.
  • 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
  • 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
  • 첫째 줄에 지민이가 잘라낸 K×K 보드를 체스판으로 만들기 위해 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
import java.util.*;
import java.io.*;

public class Step_6 {
	public static void main(String args[]) throws IOException {
		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 k = Integer.parseInt(st.nextToken());

		int[][] chess = new int[n + 1][m + 1];
		int[] lineSum = new int[m+1];
		String line;
		char tempChar;
		for (int i = 1; i <= n; i++) {
			line = br.readLine();
			for (int j = 1; j <= m; j++) {
				tempChar = line.charAt(j - 1);
				if (((i + j) % 2 == 0 && tempChar == 'B')||((i + j) % 2 == 1 && tempChar == 'W')) {//+1
					lineSum[j] = lineSum[j-1] + 1;
				} else {
					lineSum[j] = lineSum[j-1];
				}
				chess[i][j] = chess[i-1][j] + lineSum[j];
			}
		}
		int min = k*k;
		int max = 0;
		int tempInt;
		for(int i = k; i<=n; i++) {
			for(int j = k; j<=m; j++) {
				tempInt = chess[i][j] - chess[i-k][j] - chess[i][j-k] + chess[i-k][j-k];
				min = Math.min(min, tempInt);
				max = Math.max(max, tempInt);
			}
		}
		System.out.println(Math.min(min, (k*k)-max));
	}
}

A.

  • 행 열의 합의 홀수 짝수를 나누어 한 쪽만 반전하면 모든 체스판의 색이 동일한 체스판이 된다.
  • 반전 후 색이 다른 구간을 구간 합을 이용하여 구해준다.
  • k*k 구간의 구간 합은 tempInt = chess[i][j] - chess[i-k][j] - chess[i][j-k] + chess[i-k][j-k] 로 구할 수 있고, 해당 값을 임시 변수에 저장한다.
  • 해당 변수가 min보다 작은 경우, max 보다 큰 경우 갱신해준다.
  • 모든 체스 판의 경우의 수를 체크한 후 k*k-max와 min의 값 중 작은 값을 출력한다.

'백준' 카테고리의 다른 글

백준 닷컴 단계 별로 풀어보기 25단계  (1) 2023.11.01
백준 닷컴 단계 별로 풀어보기 23단계  (1) 2023.10.30
백준 닷컴 단계 별로 풀어보기 22단계  (1) 2023.10.27
백준 닷컴 단계 별로 풀어보기 21단계  (0) 2023.10.25
백준 닷컴 단계 별로 풀어보기 20단계  (1) 2023.10.23

'백준' Related Articles

티스토리툴바