boj, 백준) 21610. 마법사 상어와 비바라기(C/C++)
1. 문제 링크 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 문제 개요 N x N인 격자에서 비바라기를 연습하려고 한다. 격자의 ㅋ각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고 A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 맵의 위아래와 좌우는 연결된 것으로 본다. 비바라..
boj, 백준) 21608. 상어 초등학교 (C/C++)
1. 문제 링크 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 2. 문제 개요 교실이 하나 있다. 교실은 N x N크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N^2명이다. 학생은 1번부터 N^2번까지 번호가 매겨져 있고 (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. |r_1 - r_2 | + |c_1 - c_2| = 1을 만족하면 두 칸은 ..
boj, 백준) 1135. 뉴스전하기 (C/C++)
1. 문제 링크 https://www.acmicpc.net/problem/1135 2. 문제 개요 회사는 트리구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 모든 직원은 민식이의 직접 또는 간접적인 부하이다. 민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이것은 모든 직원이 뉴스를 들을 때까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸린느 시간의 최솟값을 구하는 프로그램을 작성하시오. 3. 문제 힌트 루트(민식)의 자식들이 루트인 서브트리를 생각해보자. 자신의 자식들이 모두 전파하는데 걸리는..
boj, 백준) 12784. 인하니카 공화국 (C/C++)
1. 문제 링크 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 2. 문제 개요 인하니카 공화국은 1번 ~ N번까지 N개의 섬으로 이루어진 나라이다. 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다. 1번 섬을 제외한 다리가 하나밖에 없는 어느 섬에서 유명한 연쇄 살인마 괴도 루팡이 자신의 목숨을 노리고 있다. 몇 개의 다리를 폭파하여, 루팡이 있을 가능성이 있는 모든 섬에서 자신의 섬으로의 모든 ..
boj, 백준) 13511. 트리와 쿼리2 ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 2. 문제 개요 N개의 정점으로 이루어진 트리가 있다. (트리 : connected acyclic undirected graph ) 정점은 1번부터 N번까지 번호가 매겨져 있다. 두 개의 쿼리를 수행하는 프로그램을 작성하자. (1) 1 u v : u에서 v로가는 경로의 비용을 출력한다. (2) 2 u v k : u에서 v로 가는 경로에 존재하는 정점 중 k번째 정점을 출력하자. 3. ..
boj, 백준) 17435. 합성함수와 쿼리 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 2. 문제 개요 함수 f : {1, 2, ...., m} → {1, 2, ..., m}이 있다. 이때 f_n : {1, 2, ...., m} → {1, 2, ..., m}을 다음과 같이 정의한다. - f_1(x) = f(x) - f_n+1(x) = f(f_n(..