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(..
boj, 백준) 11495. 격자 0 만들기 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 www.acmicpc.net 2. 문제 개요 음수가 아닌 정수들의 격자가 주어진다. - 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다. - 각 정수가 양수일 때 1 감소시킨다. 격자가 주어졌을 때 모든 정수를 0으로 만들기 위해 필요한 최소 연산의 횟수를 구하는 프로그램을 작성하시오. 3. 문제 힌트 우선, [0, 1] 을 선택했을 때, [-1, 0]이 되는 게 아닌가.. 생각했는데, 문..