본문 바로가기
반응형

Problem Solving155

백준 14621 : 나만 안되는 연애 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net [ 문제풀이 ] 결국 모든 정점을 구성하는 최소 신장 트리를 만드는 것이기 때문에 크루스칼이나 프림 알고리즘을 활용하면 쉽게 해결할 수 있다. 3가지 특징 중 2, 3번 특징은 MST를 의미하며 1번 특징만 고려해서 같은 성별의 대학교만 연결 못되도록 간선을 처리해주면 된다. import java.io.BufferedReader; import java.io.. 2021. 7. 28.
백준 2169 : 로봇 조종하기 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net [ 문제풀이 ] 처음에는 dfs + dp로 풀었는데 중복 방문 부분을 놓쳐서 TLE가 발생하였다. 해결하려고 하였지만 자꾸 실패해서 dp로 해결하였다. 왼쪽, 오른쪽, 아래쪽으로만 로봇이 움직일 수 있다는 조건을 잘 생각해보면 같은 높이에서는 절대로 좌/우측을 번갈아서 이동할 수 없다는 것을 알 수 있다. 따라서 dp 테이블을 다음과 정의하자. dp[0][i][j] : (i, j) 최댓값.. 2021. 7. 27.
백준 2613 : 숫자구슬 https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net [ 문제풀이 ] 최댓값을 구하는 최적화 문제이기 때문에 결정문제로 변경하여 파라메트릭 서치로 해결하였다. 주의해야 할 점은 l, r의 범위이다. r은 300x100으로 잡아주면 되지만 l은 1이 아닌 주어진 구슬 중 최대 번호로 해줘야 한다. 최댓값을 구하는 건 간단했는데 최댓값일 때의 각 그룹의 구슬 개수를 구하는데 상당히 애를 먹었다. 다양한 시도를 해도 안돼서 그냥 최댓값 범위를 넘지.. 2021. 7. 26.
백준 1939 : 중량제한 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net [ 문제풀이 ] 처음에는 BFS + DP로 풀려고 했는데 설계를 잘못했는지 자꾸 틀렸습니다가 나왔다. C의 범위가 굉장히 크고 최댓값을 구하는 최적화 문제이기 때문에 결정 문제로 변형할 수 있다. 따라서 파라메트릭 서치를 통해 해결하였다. import java.io.BufferedReader; import java.io.BufferedWr.. 2021. 7. 25.
백준 20040 : 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net [ 문제풀이 ] 두 노드가 같은 그래프에 속하는지를 판별해주면 되기 때문에 합집합 찾기(Union Find) 알고리즘을 사용해주면 쉽게 해결할 수 있는 문제이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; impor.. 2021. 7. 20.
백준 11812 : K진 트리 https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net [ 문제풀이 ] 두 노드의 높이를 같게 만든 후 두 노드의 번호가 다르다면 자신의 부모 노드로 올려주면서 두 노드의 번호가 같도록 만들어주면 된다. 핵심은 부모 노드의 번호를 구하는 방법인데 잘 모르겠어서 찾아보니 (자신의 번호 - 2) / K + 1이라고 한다. 주의해야 할 점은 K가 1일 경우다. 이때는 한쪽으로 몰린 트리 형태로 .. 2021. 7. 19.
백준 3980 : 선발 명단 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net [ 문제풀이 ] 선수가 11명이고 선수당 적합한 포지션의 수가 최대 5밖에 안되기 때문에 백트래킹을 통해 모든 경우를 탐색해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.u.. 2021. 7. 17.
백준 9935 : 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [ 문제풀이 ] 주어진 문자열의 길이가 최대 1000000이기 때문에 문자열에서 폭발 문자열이 존재하지 않을 때까지 탐색 후 제거하는 방법으로는 TLE가 발생하게 된다. 해당 문제는 한번의 탐색으로 탐색 및 제거를 처리해줘야 하는데 이는 스택 자료구조를 활용하면 해결할 수 있다. 문자열을 처음부터 탐색하다가 폭발 문자열의 마지막 문자를 만나게되면 스택의 Top부터 역으로 폭발 문자열.. 2021. 7. 16.
백준 3151 : 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net [ 문제풀이 ] 예전에 풀어봤던 두용액문제랑 비슷한 유형인 것 같다. 3명의 코딩 실력 합이 0이 되어야 하기 때문에 2명의 코딩 실력을 선택하고 이들의 합을 0으로 만들 수 있는 코딩 실력을 가진 사람을 남은 범위에서 이분 탐색을 통해 찾아낸다. 다만, 정답이 될 수 있는 사람이 1명 이상일 수 있기 때문에 중복값의 범위를 탐색하기 위해 이분 탐색이 아닌 LowerBound와 UpperBound를 활.. 2021. 7. 12.
반응형

티스토리툴바