본문 바로가기

PS

 (26)
[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)를 왼쪽 아래 꼭지점으로 가지고 정확히..
[ICPC 본선 대비 뇌셋] Day 2 백준 5258번 trapezoid www.acmicpc.net/problem/5258 5258번: trapezoid Consider two arbitrarily chosen horizontal lines. A trapezoid Ti between these lines has two vertices situated on the upper line and the other two vertices on the lower line (see figure below). We will denote by ai, bi, ci and di the upper left, upper righ www.acmicpc.net 문제해석이 틀릴것을 우려한 레프가 문제를 설명해주셨다.. [풀이] independent set을 구하는 문제..
[ICPC 본선 대비 뇌셋] Day 1 백준 16710 Dragging www.acmicpc.net/problem/16710 16710번: Dragging 첫 줄에 N, M, K가 사이에 공백을 두고 순서대로 주어진다. (1 ≤ N ≤ 2 × 105, 0 ≤ M ≤ 5 × 105, 0 ≤ K ≤ 5 × 105) 두 번째 줄에는 C1, C2, ... CN 이 사이에 공백을 두고 순서대로 주어진다. (0 ≤ Ci � www.acmicpc.net 난이도를 안보고 푸는 연습을 하면 좋을 것 같으므로, 당분간 솔브닥을 끄고 문제를 푼다. 풀이는 뇌에서 생각한 경로 -> 남을 위한 설명 -> (필요하다면)코딩을 위한 설명 순으로 전개할 예정. [풀이] 1차원 배열로 생각해보았으나 충분히 쉽지 않아 다음과 같이 문제를 쉽게 했다. (처음에는 k = 1인 ..
ICPC 본선 대비 ICPC를 위해 PS뇌셋을 돌 예정이다. 예선에서 문제를 풀었음에도 생각정리가 끝까지 되지 않아 혼란을 빚었다. 그래서 지금은 Tamref가 문제를 추천하면 문제풀이를 떠올리고 코드를 짤 수 있을정도까지 정리하는 연습을 하려고 한다. 하루에 한문제 이상씩 꾸준히 올리고 싶다고 하면 블로그니까 좀 빡세게 하지 않을까해서 개설했다. 최대한 다양한 문제를 풀면 좋을듯. 올해 본선은 1인분을 했으면 좋겠다.

티스토리툴바