1. 출처 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 이 문제는 내 머릿속으로는 너무 복잡하게 설계가 되어서 30분 정도 삽질하다가 결국 설계안을 찾아봤다. 똑똑한 설계안이 있어서 나는 그 설계안을 이해하고, 내 코드로 만들었다. 오늘부터는 BufferedReader를 사용해 입력을 받아 시간을 줄여볼 예정이다. 2. 설계 결국 가장 높은 합을 가져야 하는건데... 가장 높은 합 즉, 값을 가지려면 큰 자릿수에 있는 알파벳에 높은 수가 매칭되어야한다. 아이디어는 알고나면 간단하다. 하나에 알파벳에 ..
문제가 넘나 헷갈렸던 문제... 이 문제에 얼마나 시간을 쓴건지... ㅠㅠ 1. 출처 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 www.acmicpc.net 2. 설계 간단하다. 일단 나는 우선순위큐를 써서 프랫을 높은 순으로 정렬해줬다. 정렬의 경우 Comparable을 이용했다. public static class Node implements Comparable{ int line; int flat; public Node(int line, int flat){ this.line = line;..
오랜만에 강적 문제를 만났다... 1. 출처 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 설계 혼자서는 설계하기 어려웠던 문제이다. 그래서 유튜브의 힘을 좀 빌렸다. 감사합니다 코데풀님... 영상을 보니 어느정도 설계 가닥이 잡혔다. 1) (0,0)부터 부메랑의 중심지를 잡는다. 2) 부메랑을 만드려고 하는 위치 3곳이 visited되었는지 체크한다. 3) 4개 모양의 부메랑 중 가능한 부메랑을 찾는다. 단, 한 중심지에서 모든 부메랑의 경우를 볼 것이다. static int[][] ..
1. 출처 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 설계 문제 이해 - N개의 섬이 있고, 각 섬에는 한 사람씩 살고 있다. - 파티는 X번 섬에서 열린다. (X섬 중 1개) - 각 친구들은 각자 사는 섬에서 파티 가는길 + 다시 집으로 오는 길 = 최단거리를 구하고 각 친구들의 왔다갔다 한 거리 중 가장 멀었던 곳을 선정하는 것이다. 1) 모든 섬을 다 안 거쳐도 된다. 2) 최단 거리를 구한다. -> 프림이 아니고, 다익스트라를 쓰자! 설계 - 다익스트라는 알고리..
쉬울 줄 알고 덤볐다가 구현력에 한계를 느낀 문제이다. 알고보니 삼성 기출문제였다는 소리를 본 것 같다 ^__^... 1. 출처 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 설계 처음에는 쉬운 문제인 줄 알았던 이유가 각 감시카메라에 대해 많은 영역을 커버할 수 있는 방향을 정하고, 커버 영역을 세서 남은 영역에 대한 최소값을 구하고자 했다. 그런데, 이렇게 하면 다른 감시 카메라가 감시했던 영역도 또 감시했다고 체크해서 전체 영역이 20개인데, 감시 영역이 20을 훌쩍 넘어버릴 수 있다. ..
1. 출처 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 2. 설계 먼저 나는 카드의 조합을 생각했다. 만약 카드가 1,2,3,4가 있다고 할 때, 1과 2를 선택해서 12를 만드는 것과 2와 1을 선택해서 21을 만드는 것을 구분해야 한다고 생각했다. 그래서 순열을 써야한다고 생각했다. (만약 12, 21이 같다고 생각했다면 조합을 써야했다.) 1) 순열 설계 package BJ5568; import java.util.Scanner; public class 카드놓기 { static int n; static int k; static int[] nums; static boolean[] sel; //이미 ..
2달 전에 맞췄던 문제, 또 풀어본다. 너무 오랜만에 알고리즘을 푸니... static 쓰는 것도 까먹는 나... 오늘은 오랜만에 MST 문제를 풀어보았다. 다시 개념을 살펴보자면 MST는 최소신장트리이다. 신장 트리 중에 사용된 간선들의 가중치 합이 최소인 트리이다. 도로망, 통신망, 유통망 등 비용을 최소로 해야 이익을 볼 수 있을 때 사용한다. 대표적인 방법으로 크루스칼과 프림이 있는데, 오늘의 문제는 합집합 연산을 하고, 같은 부모를 갖는지 확인해야하는 작업이었기 때문에 딱히 MST 문제는 아니지만, 크루스칼이 적격이라고 생각해서 크루스칼로 풀었다. 2달 전에 나도 크루스칼로 풀었다는 사실! ^^ 1. 출처 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\},..
어제밤부터 고민하고 고민하던 문제! 이제는 그냥 외워야겠다라고 싶을 만큼 도전했다 ㅎㅎ.. 1. 출처 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 2. 설계 처음에는 조상이라고 해서 크루스칼로도 생각해봤는데, 그건 찐 조상! 나의 최상위 조상을 찾아주는 알고리즘이기 때문에 아니라고 생각했다. 그 후에는 트리를 직접 만들어서 같은 두 노드를 같은 depth로 만들어 준 후 함께 올라가는 시나..
