티스토리 뷰
목차
1. 촌수계산(2644)
👉 소스코드
public class Main {
static int total, personA, personB, person;
static int result = -1;
static int[][] graph;
static int[] dist;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
total = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
personA = Integer.parseInt(st.nextToken());
personB = Integer.parseInt(st.nextToken());
person = Integer.parseInt(br.readLine());
graph = new int[total + 1][total + 1];
dist = new int[total + 1];
for(int i = 1; i < person + 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a][b] = graph[b][a] = 1;
}
bfs(personA, personB);
}
public static void bfs(int x, int y) {
Queue<Integer> q = new LinkedList<Integer>();
q.offer(x);
while(!q.isEmpty()) {
int tmp = q.poll();
if(tmp == y) {
result = dist[y];
break;
}
for(int i = 1; i < total + 1; i++) {
if(dist[i] == 0 && graph[tmp][i] == 1) {
q.offer(i);
dist[i] = dist[tmp] + 1;
}
}
}
}
}- 인접행렬으로 bfs로 풀이
2. 연결 요소의 개수(11724)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, cnt;
static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
static boolean[] visited;
static boolean flag = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
visited = new boolean[N];
for(int i = 0; i < N; i++) {
map.add(new ArrayList<Integer>());
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken())-1;
int y = Integer.parseInt(st.nextToken())-1;
map.get(x).add(y);
map.get(y).add(x);
}
int count = 0;
for(int i = 0; i < map.size(); i++) {
if(!visited[i]) {
bfs(i);
count++;
}
}
System.out.println(count);
}
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<Integer>();
visited[start] = true;
q.offer(start);
while(!q.isEmpty()) {
int cur = q.poll();
for(int next : map.get(cur)) {
if(!visited[next]) {
visited[next] = true;
q.offer(next);
}
}
}
}
}- 정점들이 연결된 연결 요소의 개수를 탐색하는 문제 -> bfs 방식으로 풀이 진행
3. 가장 긴 감소하는 부분 수열(11722)
👉 소스코드
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] dp = new int[N];
Arrays.fill(dp, 1);
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int result = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < i; j++) {
if(arr[j] > arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
result = Math.max(result, dp[i]);
}
System.out.println(result);
br.close();
}
}- 일반적으로 알고 있는 LIS알고리즘이며, 접근 방식은 "감소하는"이기 때문에 입력으로 들어온 배열의 인덱스마다 모두 비교하여 j가 i보다 클 경우 해당 i인덱스의 count를 더해주어 count 값을 갱신하는 방법으로 풀이하였다. 해당 문제형식의 일반적인 풀이방식이다.
4. 격자상의 경로(10164)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] dp;
public static void main(String[] args) throws Exception {
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());
dp = new int[N + 1][M + 1];
int cnt = 1, kx = -1, ky = -1;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
if(cnt == K) {
kx = i;
ky = j;
}
cnt++;
dp[i][j] = -1;
}
}
int result = 0;
if(K == 0) {
result = recursion(1, 1, N, M);
} else {
result = recursion(1, 1, kx, ky) * recursion(kx, ky, N, M);
}
System.out.println(result);
br.close();
}
static int recursion(int n, int m, int endN, int endM) {
if(dp[n][m] != -1) {
return dp[n][m];
}
if(n == endN && m == endM) {
return 1;
}
dp[n][m] = 0;
if(n + 1 >= 1 && m >= 1 && n + 1 <= endN && m <= endM) {
dp[n][m] += recursion(n + 1, m, endN, endM);
}
if(n >= 1 && m + 1 >= 1 && n <= endN && m + 1 <= endM) {
dp[n][m] += recursion(n, m + 1, endN, endM);
}
return dp[n][m];
}
}- 1, 1부터 시작해서 이동하는 경로(우측 혹은 아래측)에 +1을 해주는 식으로 접근하였고 O표가 있는 case인 경우에는 O표가 있는 index를 기준으로 전과 후르 독립적으로 보고 각각 따로 구한뒤 곱해주는 형식으로 문제 풀이를 진행했다.
5. 사탕게임(3085)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static char[][] arr;
static int N, result = 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new char[N][N];
for(int i = 0; i < N; i++) {
String tmp = br.readLine();
for(int j = 0; j < tmp.length(); j++) {
arr[i][j] = tmp.charAt(j);
}
}
for(int i = 0; i < N - 1; i++) {
for(int j = 0; j < N; j++) {
swap(i, j, i + 1, j);
search();
swap(i + 1, j, i, j);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N - 1; j++) {
swap(i, j, i, j +1);
search();
swap(i, j + 1, i, j);
}
}
System.out.println(result);
br.close();
}
static void swap(int x, int y, int x1, int y1) {
char tmp = arr[x][y];
arr[x][y] = arr[x1][y1];
arr[x1][y1] = tmp;
}
static void search() {
for(int i = 0; i < N; i++) {
int count = 1;
for(int j = 0; j < N - 1; j++) {
if(arr[i][j] == arr[i][j + 1]) {
count++;
result = Math.max(result, count);
} else count = 1;
}
}
for(int i = 0 ; i < N; i++) {
int count = 1;
for(int j = 0; j < N - 1; j++) {
if (arr[j][i] == arr[j + 1][i]) {
count++;
result = Math.max(result, count);
} else count = 1;
}
}
}
}- 부르트포스 문제 유형으로 인정 행렬들을 행과 열로 나누어 swap하면서 counting 진행하였고, counting 할때는 최대값 갱신해주면서 최대 사탕 먹을 수 있는 개수를 구하도록 진행했다.
6. DNA 비밀번호(12891)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[] startChar = new int[4];
static int[] stringCnt = new int[4];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
String s = br.readLine();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < 4; i++) stringCnt[i] = Integer.parseInt(st.nextToken());
int result = 0;
for(int i = 0; i < P; i++) {
if(s.charAt(i) == 'A') startChar[0]++;
if(s.charAt(i) == 'C') startChar[1]++;
if(s.charAt(i) == 'G') startChar[2]++;
if(s.charAt(i) == 'T') startChar[3]++;
}
if(check()) result++;
for(int i = P; i < S; i++) {
int point = i - P;
if(s.charAt(point) == 'A') startChar[0]--;
if(s.charAt(point) == 'C') startChar[1]--;
if(s.charAt(point) == 'G') startChar[2]--;
if(s.charAt(point) == 'T') startChar[3]--;
if(s.charAt(i) == 'A') startChar[0]++;
if(s.charAt(i) == 'C') startChar[1]++;
if(s.charAt(i) == 'G') startChar[2]++;
if(s.charAt(i) == 'T') startChar[3]++;
if(check()) result++;
}
System.out.println(result);
br.close();
}
static boolean check() {
for(int i = 0; i < 4; i++) {
if(startChar[i] < stringCnt[i]) return false;
}
return true;
}
}- 네트워크 흐름을 제어할 때 사용하는 기법으로 슬라이딩 윈도우 알고리즘을 사용하여 풀이했다. 첫번째 부분 문자열을 만들어준 뒤 탐색을 시작하는데 주의할점은 부분 문자열에서 서로 다른 부분 문자열로 이동할때 겹치는 문자열이 있을 수 있기 때문에 해당 부분을 유의하여 문제 풀이하여야 한다.
7. 추월(2002)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
HashMap<String, Integer> enterOrder = new HashMap<>();
for (int i = 0; i < N; i++) {
String car = br.readLine();
enterOrder.put(car, i);
}
int[] exitOrder = new int[N];
for (int i = 0; i < N; i++) {
String car = br.readLine();
exitOrder[i] = enterOrder.get(car);
}
int result = 0;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (exitOrder[i] > exitOrder[j]) {
result++;
break;
}
}
}
System.out.println(result);
br.close();
}
}- 처음에 문제를 읽고 간단하다고 생각하고 대근이와 영식이의 차량 번호를 각 자료구조에 저장하고 index로 순서만 비교하여 문제를 풀이하였는데 상대적인 상황을 고려하지 못했다. 즉, 내가 풀이한대로 보면 이미 터널을 나간 차량의 비교가 누락되게 되는데, 케이스의 값은 제대로 나와도 풀이한 소스 코드를 제출하면 틀렸다고 나왔다. 들어온 차량의 index를 저장하여 나간 차량까지의 케이스까지 탐색하면서 풀이하는 방식으로 변경하였다.
8. -2진수(2089)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
if(N == 0) {
sb.append(0);
} else {
while(N != 1) {
sb.append(Math.abs(N % -2));
N = (int)(Math.ceil((double) N / -2));
}
sb.append(N);
}
System.out.println(sb.reverse());
br.close();
}
}- 아래 사항에 유의하여 풀이를 진행했다.
- 일반적인 2진법과 동일하게 몫이 1일때까지 나누기를 반복한다.
- 음수 나누기를 진행하기 때문에 소수점에서 올림해줘야 한다. -> Math.ceil
- N = 1이 되면 while문을 빠져나오고 마지막 몫이 1인 N을 append 해준다.
- 나눈 값들은 역순으로 builder에 들어갔기 때문에 뒤집어준다.
8. 과일 탕후루(30804)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int left = 0, maxLength = 0;
for(int right = 0; right < N; right++) {
map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);
while(map.size() > 2) {
map.put(arr[left], map.get(arr[left]) - 1);
if(map.get(arr[left]) == 0) map.remove(arr[left]);
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
System.out.println(maxLength);
br.close();
}
}- 2가지의 수로만 구성된 수열의 최대 길이 구하는 문제로써 투포인터를 알고리즘을 이용하여 문제 풀이를 진행했다.
수가 2가지인지 확인하기 위하여 map 자료 구조를 활용하여 수의 가지수를 체크하였다. 반복문을 돌리면서 탕후루인 숫자를 넣어주고 탕후루 과일의 개수가 2개 초과되면 while문 안에서 포인터를 옮겨가며 탕후루를 제거하고 최댓값을 갱신해주었다.
9. 타일링(1793)
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str;
BigInteger[] dp = new BigInteger[251];
dp[0] = new BigInteger("1");
dp[1] = new BigInteger("1");
dp[2] = new BigInteger("3");
for(int i = 3; i <= 250; i++) {
dp[i] = dp[i - 1].add(dp[i - 2].multiply(new BigInteger("2")));
}
while((str = br.readLine()) != null) {
bw.write(dp[Integer.parseInt(str)] + "\n");
}
bw.flush();
bw.close();
br.close();
}
}- 해당 문제의 point는 아래 2가지이다.
- 타일이 0개, 1개, 2개, 3개일때를 배열에 기록하고 점화식을 찾으면 된다.
- dp[i] = dp[i - 1] + 2 * dp[i - 2];
- 수가 뒤로 갈수록 커지기 때문에 BigInteger를 사용해야 한다.
- 타일이 0개, 1개, 2개, 3개일때를 배열에 기록하고 점화식을 찾으면 된다.
10. 지구 온난화(5212)
👉 소스코드
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int[] moveR = {1, -1, 0, 0};
static int[] moveC = {0, 0, -1, 1};
static char[][] map;
static boolean[][] check;
static int R, C;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
check = new boolean[R][C];
for(int i = 0; i < R; i++) {
char[] tmp = br.readLine().toCharArray();
for(int j = 0; j < C; j++) {
map[i][j] = tmp[j];
}
}
int up = R, down = 0, left = C, right = 0;
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
if(map[i][j] == 'X') {
if(find(i, j, 0) >= 3) {
map[i][j] = '.';
check[i][j] = true;
}
}
if(map[i][j] == 'X') {
up = Math.min(up, i);
down = Math.max(down, i);
left = Math.min(left, j);
right = Math.max(right, j);
}
}
}
for(int i = up; i <= down; i++) {
for(int j = left; j <= right; j++) {
bw.write(map[i][j]);
}
bw.write('\n');
}
bw.flush();
bw.close();
br.close();
}
static int find(int r, int c, int count) {
for(int i = 0; i < 4; i++) {
int nextR = r + moveR[i];
int nextC = c + moveC[i];
if(nextR < 0 || nextC < 0 || nextR >= R || nextC >= C) {
count++;
continue;
}
if(map[nextR][nextC] == '.' && !check[nextR][nextC]) count++;
}
return count;
}
}- 문제에서 요구하는 대로 시뮬레이션을 통하여 답을 도출했다. 50년후를 구현해주고 출력하면 되는 간단한 문제
- 'X' 이면서 인접한 세면 또는 네면이 바다라면 해당 i, j를 'X' -> '.' 변경
- 새로운 지도를 그려야 하는 범위를 지속해서 갱신
- 새로운 지도의 범위 출력
11. 싸이버개강총회(19583)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String sTime = st.nextToken();
String eTime = st.nextToken();
String qTime = st.nextToken();
HashSet<String> check = new HashSet<String>();
HashSet<String> result = new HashSet<String>();
String tmp;
while((tmp = br.readLine()) != null) {
int spaceIdx = tmp.indexOf(' ');
String date = tmp.substring(0, spaceIdx);
String name = tmp.substring(spaceIdx + 1);
if(date.compareTo(sTime) <= 0) check.add(name);
else if(date.compareTo(eTime) >= 0 && date.compareTo(qTime) <= 0) {
if(check.contains(name)) result.add(name);
}
}
System.out.println(result.size());
br.close();
}
}- 처음에 HashMap으로 풀이를 했다가 시초가나서 HashSet으로 변경하였다. 대용량 입력이 있음에 따라 O(n)까지도 걸릴 수 있음을 고려하지 못했다. 입력이 있을때까지 반복해서 시간을 비교하여 result에 넣어주는 식으로 문제를 해결하였다.
12. 222-풀링(17829)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
map = new int[N][N];
StringTokenizer st;
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(pooling(0, 0, N));
br.close();
}
static int pooling(int x, int y, int size) {
if(size == 2) {
int[] arr = new int[4];
int idx = 0;
for(int i = x; i < x + 2; i++) {
for(int j = y; j < y + 2; j++) {
arr[idx++] = map[i][j];
}
}
Arrays.sort(arr);
return arr[2];
} else {
int[] arr = new int[4];
size /= 2;
arr[0] = pooling(x, y, size);
arr[1] = pooling(x, y + size, size);
arr[2] = pooling(x + size, y, size);
arr[3] = pooling(x + size, y + size, size);
Arrays.sort(arr);
return arr[2];
}
}
}- 정사각형이 4x4일때와 아닐때를 구분하여 값을 구하는 방식으로 풀이했다.
13. 양 한마리... 양 두마리...(11123)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static char[][] map;
static boolean[][] visited;
static int[] moveX = {-1, 1, 0, 0};
static int[] moveY = {0, 0, -1, 1};
static int H, W;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
while(T-- > 0) {
st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
map = new char[H][W];
visited = new boolean[H][W];
for(int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
char[] tmp = st.nextToken().toCharArray();
for(int j = 0; j < W; j++) {
map[i][j] = tmp[j];
}
}
int count = 0;
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
if(!visited[i][j] && map[i][j] == '#') {
// dfs(i, j);
bfs(i, j);
count++;
}
}
}
sb.append(count).append("\n");
}
System.out.println(sb.toString());
br.close();
}
static void dfs(int x, int y) {
visited[x][y] = true;
for(int i = 0; i < 4; i++) {
int nextX = x + moveX[i];
int nextY = y + moveY[i];
if(nextX < 0 || nextX >= H || nextY < 0 || nextY >= W) continue;
if(visited[nextX][nextY]) continue;
if(map[nextX][nextY] == '#') {
dfs(nextX, nextY);
}
}
}
static void bfs(int x, int y) {
visited[x][y] = true;
Queue<Point> q = new LinkedList<Point>();
q.offer(new Point(x, y));
while(!q.isEmpty()) {
Point p = q.poll();
int curX = p.x;
int curY = p.y;
for(int i = 0; i < 4; i++) {
int nextX = curX + moveX[i];
int nextY = curY + moveY[i];
if(nextX < 0 || nextX >= H || nextY < 0 || nextY >= W) continue;
if(!visited[nextX][nextY] && map[nextX][nextY] == '#') {
visited[nextX][nextY] = true;
q.offer(new Point(nextX, nextY));
}
}
}
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}- 기본적인 그래프 탐색 문제로 bfs, dfs 두 가지로 풀이를 진행했다. '#'이면 탐색하여 방문처리해주고 양의 무리인 '#'을 탐색 시잘할 때 counting 하여 출력했다.
14. 소가 길을 건너간 이유 5(14465)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
boolean[] road = new boolean[N + 1];
for(int i = 0; i < B; i++) {
road[Integer.parseInt(br.readLine())] = true;
}
int broken = 0;
for (int i = 1; i <= K; i++) {
if (road[i]) broken++;
}
int result = broken;
for (int i = K + 1; i <= N; i++) {
if (road[i]) broken++;
if (road[i - K]) broken--;
result = Math.min(result, broken);
}
System.out.println(result);
br.close();
}
}- 초기 K구간에 고장난 신호등을 카운팅해서 broken에 담아준뒤, 초기 K구간부터 한칸씩 옆으로 이동하며 존재하는 모든 K구간을 탐색한다. 해당 K구간에서 끝점(road[i])과 시작점(road[i - K])을 확인하여 고장난 신호등의 개수를 갱신해주며 정답또한 마찬가지로 갱신하여준다.
15. 민균이의 계략(11568)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] dp = new int[N];
Arrays.fill(dp, 1);
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int result = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < i; j++) {
if(arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
result = Math.max(result, dp[i]);
}
System.out.println(result);
br.close();
}
}- 가장 긴 증가하는 수열의 기본적인 문제로 LIS 알고리즘을 적용하여 풀이했다. 이전 수가(arr[j]) 작다면 dp 배열에 해당 인덱스 값을 갱신해준다.
16. K번째 소수(15965)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
boolean[] arr = new boolean[10000001];
arr[0] = arr[1] = true;
for(int i = 2; i * i <= 10000000; i++) {
if(!arr[i]) {
for(int j = i*i; j <= 10000000; j+=i) {
arr[j] = true;
}
}
}
int num = 1;
for(int i = 2; i <= 10000000; i++) {
if(!arr[i]) {
if(N == num) {
System.out.println(i);
break;
} else num++;
}
}
br.close();
}
}- 간단한 소수 문제로 에라토스테네스의 체를 이용하여 풀이를 하였다. 범위를 10000000로 한이유는 500000번째 소수까지 처리가 되어야 하기 때문에 안전하게 해당 범위로 설정하였다.
17. KCPC(3758)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
while(N-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
KCPC[] list = new KCPC[n];
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int teamId = Integer.parseInt(st.nextToken());
int proNo = Integer.parseInt(st.nextToken());
int num = Integer.parseInt(st.nextToken());
if(list[teamId - 1] == null) {
list[teamId - 1] = new KCPC();
list[teamId - 1].id = teamId;
list[teamId - 1].scoreList = new int[k + 1];
}
list[teamId - 1].scoreList[proNo] = Math.max(num, list[teamId - 1].scoreList[proNo]);
list[teamId - 1].submitNum++;
list[teamId - 1].lastSubmit = i;
}
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = 1; j <= k; j++) {
sum += list[i].scoreList[j];
}
list[i].totalScore = sum;
}
Arrays.sort(list, new Comparator<KCPC>() {
@Override
public int compare(KCPC o1, KCPC o2) {
if(o1.totalScore == o2.totalScore) {
if(o1.submitNum == o2.submitNum) {
return o1.lastSubmit - o2.lastSubmit;
}
return o1.submitNum - o2.submitNum;
}
return o2.totalScore - o1.totalScore;
}
});
for(int i = 0; i < n; i++) {
if(list[i].id == t) {
bw.append((i + 1) + "\n");
}
}
}
bw.flush();
bw.close();
br.close();
}
static class KCPC {
int id;
int[] scoreList;
int submitNum;
int lastSubmit;
int totalScore;
}
}- 클래스 정의하여 id, 점수 리스트, 제출횟수, 마지막 제출한 순서, 총 점수를 저장하고 문제에서 요구하는 우선순위에 따라 compare로 비교하여 순서를 정렬해주었다.
18. 자원 캐기(14430)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
static int N, M;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
int left = (j-1 < 0) ? 0 : map[i][j -1];
int up = (i-1 < 0) ? 0 : map[i -1][j];
map[i][j] += Math.max(left, up);
}
}
System.out.println(map[N -1][M - 1]);
br.close();
}
}- 전형적인 DP 문제로 i, j를 기준으로 좌측인 i, j - 1과 상단인 i - 1, j 중 큰 값을 메모이제이션 해주면서 n,m인 좌표의 값을 출력
19. 이상한 술집(13702)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
long[] drinks = new long[N];
long min = 1;
long max = 0;
long res = 0;
for(int i = 0; i < N; i++) {
drinks[i] = Long.parseLong(br.readLine());
max = Math.max(drinks[i], max);
}
while(min <= max) {
long mid = (min + max) / 2;
int sum = 0;
for(long drink : drinks) {
sum += (drink / mid) ;
}
if(sum >= K) {
res = mid;
min = mid + 1;
} else max = mid - 1;
}
System.out.println(res);
br.close();
}
}- 매개변수 탐색 문제로 막걸리를 탐색하면서 중간값인(mid)로 나누면서 sum에 누적시킨다. sum이 인원수랑 같거나 크면 min을 높주면서 탐색 범위를 조정한다. 반대로 값이 작다면 max 값을 줄여서 탐색 범위를 조절한다.
20. 그대, 그머가 되어(14496)
👉 소스코드
--인접행렬 + BFS
import java.io.*;
import java.util.*;
public class Main {
static int[][] graph;
static boolean[] visited;
static int a, b, N, M, res = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new int[N + 1][N + 1];
visited = new boolean[N + 1];
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
graph[x][y] = graph[y][x] = 1;
}
bfs(a);
System.out.println(res);
br.close();
}
static void bfs(int start) {
visited[start] = true;
Queue<Point> q = new LinkedList<Point>( );
q.offer(new Point(start, 0));
while(!q.isEmpty()) {
Point point = q.poll();
int node = point.node;
if(node == b) {
res = point.cnt;
return;
}
for(int i = 1; i <= N; i++) {
if(graph[node][i] == 1 && !visited[i]) {
q.offer(new Point(i, point.cnt + 1));
visited[i] = true;
}
}
}
}
static class Point {
int node;
int cnt;
public Point(int node, int cnt) {
this.node = node;
this.cnt = cnt;
}
}
}
-- 인접 리스트 + BFS
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
static int[] dist;
static int a, b, N, M, res = -1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i = 0; i <= N; i++) graph.add(new ArrayList<Integer>());
dist = new int[N + 1];
Arrays.fill(dist, -1);
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
graph.get(x).add(y);
graph.get(y).add(x);
}
bfs(a);
System.out.println(res);
br.close();
}
static void bfs(int start) {
Queue<Integer> q = new LinkedList<Integer>( );
q.offer(start);
dist[start] = 0;
while(!q.isEmpty()) {
int node = q.poll();
if(node == b) {
res = dist[node];
return;
}
for(int next : graph.get(node)) {
if(dist[next] == -1) {
q.offer(next);
dist[next] = dist[node] + 1;
}
}
}
}
}- 문제에서 요구하는 a 문자를 b문자로 바꾼다는 부분을 이해하는데 시간이 조금 걸렸다.. a에서 b까지 가는 최단거리를 구하는 문제로 인접 행렬 + BFS, 인접 리스트 + BFS 두 가지로 풀이 하였다.
21. 점프 점프(14248)
👉 소스코드
-- dfs
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static boolean[] visited;
static int N, s, cnt = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
visited = new boolean[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
s = Integer.parseInt(br.readLine());
dfs(s);
System.out.println(cnt);
br.close();
}
static void dfs(int node) {
if(N < node || 1 > node || visited[node]) return;
visited[node] = true;
cnt++;
dfs(node + arr[node]);
dfs(node - arr[node]);
}
}
--bfs
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static boolean[] visited;
static int N, s, cnt = 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
visited = new boolean[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
s = Integer.parseInt(br.readLine());
bfs(s);
System.out.println(cnt);
br.close();
}
static void bfs(int node) {
visited[node] = true;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(node + arr[node]);
q.offer(node - arr[node]);
while(!q.isEmpty()) {
int next = q.poll();
if(N < next || 1 > next || visited[next]) continue;
visited[next] = true;
cnt++;
q.offer(next + arr[next]);
q.offer(next - arr[next]);
}
}
}- 각 돌을 노드로 인지하고 좌우로 이동하는 것을 간선이라고 생각하는 부분에서 시간이 조금 길어졌다. 간단하게 이동할 수 있는 영역을 탐색해주면 되는 문제였다. 방식은 dfs, bfs 모두 사용하여 풀이를 진행했다.
22. 폴짝폴짝(1326)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static boolean[] visited;
static int N;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
visited = new boolean[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
System.out.println(bfs(a, b));
br.close();
}
static int bfs(int a, int b) {
Queue<Frog> q = new LinkedList<Frog>();
q.offer(new Frog(a, 0));
visited[a] = true;
while(!q.isEmpty()) {
Frog frog = q.poll();
if(frog.frog == b) return frog.cnt;
int step = arr[frog.frog];
for(int i = frog.frog; i >= 1; i -= step) {
if(visited[i]) continue;
visited[i] = true;
q.offer(new Frog(i, frog.cnt + 1));
}
for(int i = frog.frog; i <= N; i += step) {
if(visited[i]) continue;
visited[i] = true;
q.offer(new Frog(i, frog.cnt + 1));
}
}
return -1;
}
static class Frog {
int frog;
int cnt;
public Frog(int frog, int cnt) {
this.frog = frog;
this.cnt = cnt;
}
}
}- start 지점인 a를 시작으로 b까지 최소 횟수로 가는 문제인데 왼쪽도 갈 수 있다는 점을 감안하여 풀이를 해야한다. 그래서 좌우로 가는 case를 나눠서 풀이를 진행하였고, 처음에 배수라는 부분을 잘못 인지하고 풀이했다. 배수라는 부분을 잘 인지하여 -=, += 로 풀이를 진행하여야 한다.
23. 파닭파닭(14627)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
int [] arr = new int[S];
long end = 0, start = 1, res = 0, pa = 0;
for(int i = 0; i < S; i++) {
arr[i] = Integer.parseInt(br.readLine());
pa += arr[i];
end = Math.max(arr[i], end);
}
while(start <= end) {
long mid = (start + end) / 2;
int sum = 0;
for(int i = 0; i < S; i++) {
sum += (arr[i] / mid);
}
if(C <= sum) {
res = mid;
start = mid + 1;
}
else end = mid - 1;
}
System.out.println(pa - (res * C));
br.close();
}
}- sum에다가 중간값인 mid로 나눠가면서 최적의 파 값을 탐색한다. 그리고 최적의 파를 사용해야 할 파닭의 수인 C 값과 비교하면서 같거나 크면 범위를 뒤로 땡겨주고 파닭의 수보다 작다면 범위를 뒤에서 앞으로 당겨서 탐색을 진행한 뒤 전체 사용해야 할 파에서 최적의 파 * 파닭의 수를 빼서 라면에 넣을 파를 계산해야 한다. 나 같은 경우 mod 연산으로 남는 파를 계산하는 식으로 풀이를 했는데 맞왜틀을 외쳐서 한참 쳐다봤다..
24. 풍선 공장(15810)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int staff = Integer.parseInt(st.nextToken());
int ballons = Integer.parseInt(st.nextToken());
int[] staffs = new int[staff];
long start = 0;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < staff; i++) {
staffs[i] = Integer.parseInt(st.nextToken());
}
// long end = Arrays.stream(staffs).min().getAsInt() * ballons;
Arrays.sort(staffs);
long end = (long)staffs[0] * (long) ballons;
long res = 0;
while(start <= end) {
long mid = (end + start) / 2;
long sum = 0;
for(int i = 0; i < staff; i++) {
sum += (mid / staffs[i]);
}
if(sum >= ballons) {
res = mid;
end = mid - 1;
} else start = mid + 1;
}
System.out.println(res);
}
}- 풍선을 하나 만드는게 가장 적게 걸리는 사람이 모든 풍선에 바람을 불 때 걸리는 시간이 탐색 범위가 되는데 해당 값을 구해올 때 Steram을 써서 계속해서 59%에서 틀렸다고 나왔다. 결국에는 end의 범위가 최악에는 스태프 한명이 풍선을 부는데 걸리는 시간이 100만, 불어야 하는 풍선의 개수가 100만이라고 했을 때 end의 범위는 1조가 되기 때문에 타입은 long이여야 하는데 getAsInt()는 Int형을 반환하기 때문에 틀렸다고 나왔다. 직관적인 풀이를 지향해야겠다