공부공간

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 원자들이 이동하면서 충돌하면 그 에너지의 누적합을 구하는 문제이다. 사실 구현자체는 어렵지 않았지만, 구현을 쉽게하려고 배열을 많이 쓴다던가, For문을 많이 돌리게되면 시간초과에 벽에 마주하게된다. 그렇다면 어떻게 시간초과를 줄일까? 1. 썼던 배열을 최대한 재사용하자 2. for문의 범위를 최대한으로 줄이고, 범위를 벗어나는 케이스에대해서 처리를 해주자. 3. Heap영역에 최소한으로 다가가자...

2048게임을 그대로 만들면된다. DFS를 돌면서 현재 맵을 변형한 것을 인자로 넘겨주면서 5번까지 돌면서 가장 큰값을 리턴해주면된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int answer = 0,N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 보호필름에는 층이 존재하는데, 이층은 가로 W ,세로 D의 크기를 가진다. 검사합격 기준 K가 주어질때, 0부터 W-1까지의 열에서 연속해 같은숫자가 K개 주어지면 그 열은 합격기준을 통과한다 초기에 통과기준을 넘지못하면, 약품을 투입해서 세로 D중 몇개를 한문자로 바꿀수 있다. 최소한의 약품을 사용하여 합격기준을 통과하고 싶을때, 최소한의 약품의 수를 구하는 문제이다. 문제는 간단하다. 최소한의 ..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net N개의 층이 있는 원판을 M등분하여, 각층에 숫자를 넣고, K번의 회전연산을 통하여 답을 구하는 문제이다. 각 회전연산마다 이웃한..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 선거 구를 나누기 위해서, 주어진 조건에 따라서 5번 선거구를 먼저 지정한 후에, 해당 경계선에 따라 나머지 선거구를 나누어준다..

연구소 문제 시리즈 중 마지막이 아닐까? 바이러스의 개수 중 M개를 선택하여 BFS를 진행하면된다. 만약 처음에 선택되지 않은 바이러스를 중간에만나면 그 바이러스도 활성상태가되어 상하좌우 뻗어가는 문제이다. 비활성에서 활성으로 변할때 1초가 소요되므로 따로 처리해주지않고 진행한다. 맵에 더이상 진행할 곳이 없거나, 서브셋으로 선택하여도 바이러스로 모두 채울수 없을때에 해당 ANSWER값을 출력한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparato..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net 플로이드-워셜문제의 기본적인 형태이다. 그래프에서 전체의 최단경로를 구할때에 O(N^3)으로 구할수있다. For문을 돌면서 나와 인접..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 상당히 쫄았던 문제이다.. Union-Find 개념을 이용하여 접근하려니 접근방법이 잘 보이지 않았고, 워스트케이스에대해서 0.5초의 시간을 넘을 것같다는 생각이 들었다. 일단한번 서브셋을 구해서 나누어보자! 라는 생각으로 접근하였는데, 단순한 2번의 BFS로 해결되었다. 문제에 쫄면 안되겠다. import java.io.BufferedReader; import java.io.InputStreamReader; impo..