www.castlehi.com

문제 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 티어 소요 시간 50분 분류 세그먼트 트리 코드 public class Main { static final int MOD = 1_000_000_007; static int[] arr; static long[] tree; public static void main(String[] args) throws IOException { Bu..

문제 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 티어 소요 시간 약 20분 분류 세그먼트 트리 코드 public class Main { static final int MIN_VALUE = 1; static final int MAX_VALUE = 1_000_000_000; static int n, m; static int[] minTree; static int[] maxTree; static int[] ..

문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 티어 분류 세그먼트 트리 코드 public class Main { static int n, m, k; static long[] arr; static long[] segmentTree; public static void main(String[] args) throws IOException { BufferedReader br = new ..

문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 티어 분류 dfs dp 코드 public class Main { static int n; static ArrayList[] graph; static boolean[] visited; static int[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = ..

문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 티어 분류 dp 코드 public class Main { static int n; static int[][] map; static int[] dx = {1, 0}; static int[] dy = {0, 1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

문제 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 티어 분류 자료구조 Deque 코드 public class Main { static StringBuilder sb = new StringBuilder(); static ArrayDeque deque = new ArrayDeque(); public static void main(String[] args) throws IOException { BufferedRea..

문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 티어 분류 bfs 코드 public class Main { static int f, s, g, u, d; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder ..

문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 티어 분류 투포인터 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder..

문제 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 티어 분류 구현 코드 public class Main { static int n; static int k; static int[][] chess; static LinkedList[][] chessPiece; static Map chessPieceMatcher = new HashMap(); static public class ChessPiece { int idx; int x, y; int ..

문제 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 티어 분류 구현 코드 public class Main { static int n; static int k; static int[][] chess; static LinkedList[][] chessPiece; static Map chessPieceMatcher = new HashMap(); static public class ChessPiece { int idx; int x, y; int di..

문제 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 티어 분류 구현 dfs 코드 import java.io.*; import java.util.*; public class Main { static int n; static int[] number; static char[] operator; static int answer = Integer.MIN_VALUE; public static void main(String[] args) ..

문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 티어 분류 구현 코드 import java.io.*; import java.util.*; public class Main { static int n; static int[][] map; static int res = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = ne..

문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 티어 분류 백트래킹 bfs 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.sql.Array; import java.util.ArrayList; import java.util.LinkedList; import java.util.StringTokenizer;..

문제 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 티어 분류 구현 코드 import java.io.*; import java.util.*; public class Main { static int[][] arr = new int[101][101]; static int yLength = 3; static int xLength = 3; public static class Number implements Comparable { int ..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 티어 분류 그래프 코드 import java.io.*; import java.util.*; class Main { static int n; static int l, r; static int[][] map; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, -1, 0, 1}; public static void main(String[..

문제 https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 티어 분류 구현 코드 import java.io.*; import java.util.StringTokenizer; public class Main { // 0 : 앞면 // 1 : 뒷면 // 2 : 윗면 // 3 : 아랫면 // 4 : 좌측면 // 5 : 우측면 static char[][][] cube; public static void main (String[]args) throws IOEx..