문제 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 전화번호를 문자열로 입력받고 이를 정렬하여 번호를 비교하는 방식으로 해결할 수 있다. 예를 들어, 예제 입력1의 테스트 케이스인 911, 97625999, 91125426을 입력받은 경우, 이를 오름차순으로 정렬하면 911, 91125426, 97625999 가 된다. 여기서 startsWith() 함수를 사용하여 이전의 번호가 다음 번호에 포함되는지 여부를 확인할 수 있다. 이를 통해 전화번호 목록이 일관성 있는 목록인지 판단..

문제 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 풀이 좌표 (1, 1)부터 시작하여 순서대로 표를 채워가도록 코드를 구성하였다. while문을 사용하여 표를 역순으로 채워준다. 다음 좌표에 숫자가 이미 채워져 있거나 탐색 범위를 벗어나는 경우 달팽이 모양으로 숫자를 채울수 있도록 방향을 바꿔준다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val size = br.readLine().to..

문제 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 단순하게 2중 for문을 사용하여 판매의 최대값을 갱신해가며 계산하는 풀이는 시간초과가 발생한다. 대신 역방향 탐색을 활용하여 해결해야 한다. 주식으로 최대의 이익을 보려면 주식을 구입한 가격과 판매하는 가격의 차이가 가장 커야 한다. 역방향 탐색을 통해 판매하는 가격의 최대값을 얻을 수 있다. 먼저 마지막으로 입력받은 가격을 최대값으로 설정하고 역방향 탐색을 시작한다. 탐색 중 현재 값이 최대값보다 작다면 둘의 차이가 얻을 수 있는 가장 ..

문제 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 풀이 문제에서 1, 1, 2, 3, 5, ... 을 보면 알 수 있듯이 정사각형 타일의 한 변의 길이는 피보나치 수열로 증가한다. 따라서 반복문을 이용하여 DP 계산을 해주면 타일의 길이를 계산할 수 있다. N개의 타일로 구성된 전체 타일은 한 변의 길이가 dp[N]이고, 다른 변의 길이는 dp[N] + dp[N-1], 즉 dp[N + 1] 이 된다. 그렇기 때문에 전체 타일의 둘레는 dp[N]*2 + dp[N+1]*2 로 구하면 된다. 코드 fun main(..

문제 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 이 문제는 MST(최소 스패닝 트리)를 구하는 것로 이번에는 크루스칼 알고리즘을 사용해서 풀이했다. 우선순위 큐를 활용하여 비용이 낮은 순서대로 길을 선택하여 MST를 만들고 사이클이 발생하는 간선은 제외해준다. MST를 만드는 과정에서 발생하는 비용들은 더해준다. MST에서 간선을 하나 지우는 것으로 마을을 두 개로 나눌 수 있다. 우선 순위 큐를 이용해 MST를 구했기 때문에 가장 마지막에 연결된 간선을 지워주..