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]이 되는 게 아닌가.. 생각했는데, 문..
boj, 백준) 11407. 책 구매하기 3 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/11407 11407번: 책 구매하기 3 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net 2. 문제 개요 총 N명의 사람이 M개의 서점에서 책을 사려고 한다. 각 사람은 사려고 하는 책의 개수가 정해져 있고 서점도 팔 수 있는 책의 개수가 정해져 있다. i번째 서점에서 j번째 사람에게 C_ij개의 책을 팔 수 있고, 이때 택배로 보내는 비용이 D_ij라고 할 때, 책을 최대 몇 권 살 수 있는지, 그리고 이때의 배송비의 합의 최솟값을 구하는 프로그램을 작성..
boj, 백준) 11406. 책 구매하기 2 ( C/C++)
1. 문제 링크 www.acmicpc.net/problem/11406 11406번: 책 구매하기 2 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net 2. 문제 개요 N명의 사람이 각자 A_j권의 책만큼 책을 구매하려고 한다. 서점은 M개가 있다. 서점에는 B_i권의 책이 있다. 사람 j가 서점 i에서 살 수 있는 최대 책의 개수는 C_ij이다. 이때, 사람들이 책을 가장 많이 사려고 할 때, 최대 몇 권까지 살 수 있는지 구하는 프로그램을 작성하시오. 3. 문제 힌트 최대유량으로 풀 수 있을 것 같다. 사람이 살 ..
boj, 백준) 17412. 도시 왕복하기1 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/17412 17412번: 도시 왕복하기 1 첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다. www.acmicpc.net 2. 문제 개요 N개의 도시가 P개의 단방향 길로 연결되어 있다. 1번 도시에서 시작해서 2번 도시로 가야 하는데, 한번 경로에 포함된 길은 다시 포함되어서는 안된다. 이때, 1번 도시에서 2번 도시까지 갈 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 3. 문제 힌트 단 한번만 가야 한다..라는 것의 의미를 다시 생각해보자. 한번 가고 나면 간선(경로, 도로)이 막히는 그런 게..
boj, 백준) 2-SAT - 1
1. 문제 링크 www.acmicpc.net/problem/11277 11277번: 2-SAT - 1 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 20)과 절의 개수 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 www.acmicpc.net 2. 문제 개요 2-SAT를 풀어보자. SAT에 대한 설명은 본문에 잘 나와있다. 3. 문제 힌트 N은 최대 20, M은 최대 100, 전수조사로 충분히 풀 수 있는 크기이다. 시간 복잡도는 모든 경우의 수 (2^20)에 대해 M개의 식을 검증하면 된다. O(2^(N)*M)인데 간당간당.. 4. 문제 풀이 dfs방식으로 모든 순열을 만들어..