문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 나는 이 문제를 조금 복잡하게 푼 것 같다. BFS를 두 개의 함수로 만들어 해결하였다. 아래와 같은 과정으로 해결하였다. 1. BFS를 통해 모든 섬을 찾고, 섬을 구별하기 위해 섬의 숫자를 1,2,3,4... 등으로 바꾼다. 또한 모든 섬의 가장자리를 따로 저장한다. 2. 따로 저장한 섬의 가장자리에서 BFS를 통해 다른 섬 까지의 최단거릴 구해서 갱신한다. 3. 최단거리를 출력한다. 코..
문제 https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 풀이 모든 수를 연결해서 풀면 시간초과 혹은 메모리 초과가 발생한다. 이 문제를 풀기 위해서는 다른 접근이 필요하다. 잘 생각해보면 아래와 같이 자릿수가 증가하면서 숫자의 갯수가 변하는 규칙을 알 수 있다. 자릿수 숫자 갯수 글자 갯수 1 9개 (1~9) 9개 2 90개 (10~99) 180개 3 900개 (100~999) 2700개 이 규칙을 이용하면 몇번째 글자가 어떤 숫자에 포함되어 있는지 알 수 있다. 예를 들어 2..
문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 이 문제는 DFS와 백트래킹을 사용하여 해결할 수 있다. DFS를 통해 모든 원소를 탐색하면서 색종이를 붙일 수 있는지 체크한다. 이때 색종이의 개수를 저장하는 배열을 하나 만들고, 색종이를 붙일 수 있다면 색종이를 붙인다. 이후 다시 dfs 탐색을 진행하는 식으로 해결하면 된다. 코드 import java.io.*; import java.util.*; public class ..
문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 나는 이 문제를 Abs라는 클래스를 만들어 해결하였다. Abs 클래스는 Comparable 인터페이스를 구현하는 클래스로, 원래 자기의 값인 int num 멤버와 절댓값인 int abs를 멤버로 갖는다. 또한 compareTo 메소드를 Override하여 절댓값(abs)을 기준으로 작은 순, 절댓값이 같다면 원래 값(num)이 작은 순으로 정렬되게 한다. 이후 Ab..
문제 https://www.acmicpc.net/problem/14431 14431번: 소수마을 첫 번째 줄에 소수 마을의 위치 (X1,Y1)와 A마을의 위치 (X2,Y2)가 입력된다. 두 번째 줄에 경유할 수 있는 마을의 개수 N (0 ≤ N ≤ 4000)가 입력된다. 세 번째 줄부터 N+2번째 줄까지 경유 할 수 있는 마 www.acmicpc.net 풀이 이 문제는 소수를 구하는 알고리즘과 다익스트라 알고리즘을 이용해 해결할 수 있다. 1. 모든 정점들의 거리를 구하면서, 거리가 소수인 정점들만 연결한다. 2. 연결한 그래프를 다익스트라 알고리즘을 통해 최단거리를 계산한다. 이때 거리가 소수인지 판단하는 것은 에라토스테네스의 체 알고리즘을 사용해 미리 소수들을 구해놓았다. 코드 HTML 삽입 미리보기..
문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 이 문제는 에라토스테네스의 체로 소수를 구한 다음, 투 포인터 알고리즘을 사용하는 것이 핵심이다. 먼저 에라토스테네스의 체를 사용하여, N까지의 모든 소수를 저장한다. 이후 투 포인터 알고리즘을 사용하기 위해 left 포인터와 right 포인터를 0으로 초기화한다. 어떤 수든 첫번째 소수는 2기 때문에 sum=2로 초기화해준다. 만약 sum이 N과 같다면 ans를 1 증가시키고, N보다 작다면 right 포인터를 오른쪽으로 한 칸 옮기고 sum에 올려준다. N보다 크다면 left 포인터가 가리키는 값을 감..
문제 https://www.acmicpc.net/problem/1531 1531번: 투명 첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌 www.acmicpc.net 풀이 처음에 문제가 잘 이해가 안됐는데 다음과 같이 그림으로 이해하면 간단하다. 예제를 예시로 들면 다음과 같다. 예제는 M이 1이였으므로, 2개 이상의 종이가 겹쳐야 그림이 보이지 않는다. 따라서 (41,41)~(60,60) 부분의 그림 400개(20*20)와, (71,71)~(80,80) 부분의 그림 100개(10*10)를 합쳐서 500개의 그림이 보이지 않는 것이다. 해결법..
문제 https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 풀이 처음 이 문제를 봤을 땐, a와 b를 -100부터 100까지만 판단해서 브루트 포스 방식으로 해결하려고 했다. 하지만 a와 b를 -10000~10000까지 전부 조사해도 틀리고, 그 이상은 시간이 엄청나게 오래걸린다. 그런데 점화식을 잘 보면, a를 쉽게 구할 수 있음을 알 수 있다. 1. arr[i+1] = arr[i]*a + b 2. arr[i] = arr[i-1]*a + b (arr[i+1]-arr[i]) = (arr[i]*a+b) - (arr[i..
문제 https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net 풀이 이 문제는 아래와 같은 제약 조건들이 존재한다. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. 벽돌들의 높이는 같을 수도 있다. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. 결국 중요한 것은 밑면의 넓이가 ..
문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 트리의 지름을 구하기 위해서는 한 가지 규칙을 찾아내야한다. 그 규칙은 바로 트리의 지름은 리프노드와 리프노드 간의 거리라는 것이다. 따라서 모든 리프 노드에서 DFS탐색을 하여 다른 리프노드까지의 거리를 구하고, 최대 거리를 갱신하면 된다. 이때, 리프노드를 구별하는 방법은 루트노드가 아니면서 연결 노드가 1개(부모노드)뿐인 노드를 구하면 된다. 리프노드를 따로 구..