본문 바로가기

전체 글

 (33)
[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)를 왼쪽 아래 꼭지점으로 가지고 정확히..

티스토리툴바