본문 바로가기

전체 글312

[JAVA] 백준 30805 - 사전 순 최대 공통 부분 수열 https://www.acmicpc.net/problem/30805주어진 두 수열의 공통 부분 수열 중 사전 순으로 가장 뒤에 있는 수열의 길이를 구하는 문제이다.먼저 주어진 수열 중 공통이 아닌 부분을 지웠고, 그 이후 최댓값을 구해 각 수열에 해당 최댓값이 몇번 나오는지 구했다. 각 수열에서 최댓값이 나온 횟수 중 작은 값(min)만큼 부분 수열이 될 수 있으니 정답 문자열에 최댓값을 min번 붙여준 뒤,각 수열에서 해당 최댓값이 min번째 나오는 위치를 구해 해당 위치 기준으로 sublist한 뒤 동일한 처리를 반복해 list가 전부 비어있을 때 탈출하는 방법으로 풀었다. import java.io.BufferedReader;import java.io.IOException;import java.io.. 2025. 9. 2.
[JAVA] 백준 9372 - 상근이의 여행 https://www.acmicpc.net/problem/9372 문제를 대충 읽고 가장 적은 종류 -> BFS! 하고 BFS 돌렸다가 깨달은 문제이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea.. 2025. 8. 30.
[JAVA] 백준 17144 - 미세먼지 안녕! https://www.acmicpc.net/problem/171442차원 배열에 있는 미세먼지가 상하좌우로 확산되면서 동시에 공기청정기로 위에서 한바퀴 밑에서 한바퀴 돌면서 공기 청정기 위아래 칸을 없애는 문제였다.위에 작성한대로 미세먼지를 확산시키고 재귀함수로 위에 한바퀴 밑에 한바퀴 배열을 밀어서 해결했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main { static int ti= -1; static int ti2 = -1; public static void main(String[] args) th.. 2025. 8. 30.
[JAVA] 백준 14938 - 서강그라운드 https://www.acmicpc.net/problem/14938갈 수 있는 최대 경로 내에 있는 정점의 value를 모두 더하는 문제이다.시작점도 모든 정점이 될 수 있고, 그 정점을 기준으로 구해야하는 최단경로도 모든 정점에 대해 구해야 하므로플로이드-워셜을 써야겠다는 생각을 했고, 쉽게 풀 수 있었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n.. 2025. 8. 29.
[JAVA] 백준 14502 - 연구소 https://www.acmicpc.net/problem/14502처음 봤을 때 dfs로 푸는 문제인건 알겠는데 벽을 세우되 꼭 세개를 세우래서 벽을 어떻게 세울까 고민을 많이 했는데 어떤 기준을 가지고 하기에는 고려할 점이 너무 많았다. [첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)]-> 지도의 넓이 범위가 생각보다 크지 않은 것을 보고 브루트 포스가 아닐까 하고 6중 포문으로 전체 탐색 후 각 케이스마다 DFS를 돌려봤는데 성공했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.. 2025. 8. 29.
[JAVA] 백준 13172 - Σ https://www.acmicpc.net/problem/13172문제 설명이 굉장히 긴 문제였지만 결론적으로 a/b를 기약분수 형태로 만들고, b의 모듈러 연산의 역원을 구해 주사위 1개 당 a * b-1 % 1000000007의 값을 구해 그 합을 구하는 문제였다. 일단 a/b를 기약분수 형태로 만들기 위해 유클리드 호제법(퍼플렉시티한테 물어봄)을 통해 최대공약수를 구하고, 페르마의 소정리 (퍼플렉시티한테 물어봄) 로 b의 모듈러 연산의 역원을 구해 이를 a에 곱해주고 나머지를 구했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public .. 2025. 8. 28.

티스토리툴바