본문 바로가기

PS/2020 ICPC 본선 대비 뇌셋

 (23)
[ICPC 본선 대비 뇌셋] Day 12 전자기 공부 할 바에야 CERC 문제들을 풀어보고 있다. 백준 13948 Dancing Disks www.acmicpc.net/problem/13948 13948번: Dancing Disks In the example above, the first 9 steps simply move all the disks, without reordering, to the rod in row 6, column 5 — immediately to the left of the target rod in the lower-right corner. In the following step, the stack of five disks from the top of the www.acmicpc.net 뭔가 아리까리 하긴 한데, 입력 수열..
[ICPC 본선 대비 뇌셋] Day 11 백준 15599번 Ascending Photo 수열을 증가하는 순서대로 만들려면 얼마나 잘라야 하는가를 묻는 문제이다. 이메이미와 탐레프는 1500바이트 선에서 정리했는데, 나는 4000바이트 코드 말고는 어떻게 짜야하는지 잘 모르겠다. 감소하는 부분이 있으면 무조건 잘라야한다. 따라서 전처리를 하여 m개의 부분연속수열들로 쪼갠다. 편의상 모든 숫자는 1부터 n까지 나타난다고 하자. 같은 숫자가 붙어있으면 그 사이를 자를필요가 없으므로, 이것 또한 전처리로 묶어 각 부분수열을 순증가하는 수열로 만들자. 또한, 여기에서 이때, 이 부분수열들을 잘라서 원래의 수열을 만든다고 생각해보자. 원래 수열에서 a와 a+1이 연속해서 나타나는 경우만 집중적으로 보자. 만약 어떠한 부분수열에서 a와 a+1이 연속해서 나..
[ICPC 본선 대비 뇌셋] Day 10 백준 16326번 Numbers www.acmicpc.net/problem/16326 16326번: Numbers In the first test, the following pairs of numbers are suitable: (5, 151), (55, 101), (101, 55), (151, 5). In the second test, the following pairs of numbers are suitable: (515, 9009), (636, 8888), (8888, 636), (9009, 515). In the third test, the following www.acmicpc.net 마찬가지로 NEERC set을 돌다가 만난 문제인데, 코딩은 좀 복잡할 것 같아 풀이만 남긴다. 레프 화이팅>y..
[ICPC 본선 대비 뇌셋] Day 9 알고리즘 시험이 끝났기 때문에 나를 막을 수 있는건 계측 뿐이다...... 오늘부터는 꾸준히 몇문제씩 올릴 예정 백준 16329번 space station www.acmicpc.net/problem/16329 16329번: Space Station The first line contains the number T, representing the number of tests. The first line that describes a test contains the three variables N M K. (1 ≤ N, M ≤ 1000) The following N–1 lines are of the form A B C (1 ≤ A ≤ B ≤ N; 0 ≤ C, K ≤ 106) www.acmicpc.net 며칠..
[ICPC 본선 대비 뇌셋] Day 8 백준 8987번 수족관 3 www.acmicpc.net/problem/8987 8987번: 수족관 3 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 그리디로 찾으면 된다. 제일 물이 많이 빠지는 것을 찾은 후, 그 다음에 물이 제일 많이 빠지는 것을 찾고, 그 과정을 반복한다. [증명] 제일 많이 빠지는 점을 S1이라고 하자. S1에서 물을 빼면 S1을 기준으로 양 옆으로 갈수록 수위가 높아진다. 그리고 이를 첫번째 수위라고 정의하자. 만약 S2, S3를 뺀 것이 S1, S2를 뺀 것보다 양이 많다고 가정..
[ICPC 본선 대비 뇌셋] Day 7 백준 4009번 순찰 www.acmicpc.net/problem/4009 4009번: 순찰 1부터 N까지 번호가 붙여진 N개의 마을과, 이들 마을을 모두 연결하는 N-1개의 도로가 있다. 각 도로는 정확히 두 마을을 연결하며, 임의의 마을로부터 다른 모든 마을까지 이들 도로들만 이용하�� www.acmicpc.net 왜인지 모르겠으나 점점 강해지는 느낌이 든다.. [관찰 1] 지름길을 하나 박으면, 두 끝 정점 사이의 최단 경로에 있는 도로는 한번만 이동해도 되며, 나머지 도로는 두번씩 지나가야 한다. [관찰 2] 지름길을 두개 박으면, 관찰 1과 비슷한 식으로 생각할때, 두 개의 최단 경로를 잡을 수 있고, 이들 중 중복되지 않는 도로는 한번씩만 이동해도 되고, 중복되거나 경로에 포함되지 않은 도로는 ..
[ICPC 본선 대비 뇌셋] Day 6 백준 1868번 보물찾기 www.acmicpc.net/problem/1868 1868번: 보물찾기 첫째 줄에 n이 주어진다. (1≤n≤50,000) 이후 n-1개의 줄에는 각각 두 개의 숫자가 주어진다. a와 b가 주어졌다면, a번 방과 b번 방 사이에 복도가 있어 왕래할 수 있다는 의미이다. 방의 번호는 1번부 www.acmicpc.net 이 문제를 본지 1주일만에 풀이를 쓰는 것 같다. 방법은 대충 생각하고 있었는데 구체화가 너무 더뎌 푸는데 오래걸렸다. 여담이지만, 내 첫 루비를 장식하게 되었다. [시도 1] 트리의 지름일 것이다. --> 반례를 찾을 수 있다. [시도 2] centroid decomposition을 하면 될 것이다. --> 반례를 찾을 수 있다. 일반적인 그리디를 통해서 문제를 접..
[ICPC 본선 대비 뇌셋] Day 5 백준 17970번 Islands www.acmicpc.net/problem/17970 17970번: Islands Your program is to read from standard input. The input starts with a line containing an integer n (5 ≤ n ≤ 100,000), where n is the number of villages in each island. The villages are numbered from 1 to n. In the following two lines, each line contains www.acmicpc.net 증명이 까다롭기는 하나 그렇게까지 어려운 문제는 아닌 것 같다. 사실상 왜 다이아 2인지는 잘 모르겠다. 물론 작년의..
[ICPC 본선 대비 뇌셋] Day 4 백준 19619번 자매도시 www.acmicpc.net/problem/19619 19619번: 자매 도시 첫번째 예제에서, N = 5, M = 6, U = [0, 0, 1, 1, 1, 2], V = [1, 2, 2, 3, 4, 3], W = [4, 4, 1, 2, 10, 3], Q = 3, X = [1, 2, 0], Y = [2, 4, 1]이다. 이 예제는 다음 그림과 같다. 그레이더는 처음에 init(5, 6, [0, 0, 1, 1, 1, 2] www.acmicpc.net 두 간선을 거리 w로 정렬한 뒤 하나씩 추가해나가면서 문제를 해결하면 된다. 역시 보물찾기를 보고 나니 다른 문제들이 쉬워보인다. 편의상 라인을 일렬로 연결된 그래프라고 부르자. w의 크기순으로 j번째 간선(거리 v[j]라고 하자)까..
[ICPC 본선 대비 뇌셋] Day 3 숙제와 시험이 너무 많고 보물찾기 문제가 너무 어려워서 못쓸뻔했지만 정원은 나름 쉬워서 먼저 풀이를 적는다. 백준 5484번 정원 www.acmicpc.net/problem/5484 5484번: 정원 재현이는 BOJ에서 가장 아름다운 정원을 소유하고 있는 사람으로, 정원에 n개의 꽃을 심어놓았다. 모든 꽃들이 화사하게 핀 여름날. 재현이는 아름다운 꽃들을 보고 있으니 갑자기 대한민국의 경 www.acmicpc.net 별로 생각 안하고 짜도 되지만 구현이 좀 더럽다. 또, 풀이에서는 1베(one based)를 쓰는 것이 이롭다는것을 느꼈다. 전처리: 모든 가능한 sub 가로줄과 sub 세로줄의 장미수를 구한다. --> 250^3 = 1e7 문제를 보는 순간 (i, j)를 왼쪽 아래 꼭지점으로 가지고 정확히..

티스토리툴바