[백준 / BOJ] 13907 세금
문제 출처 : https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 주언이는 두 도시를 오가며 무역을 한다. 이때, 도시의 통행료가 가장적은 길로 이동을 하려고한다. 도시들은 양방향으로 연결되어있으며 도로마다 통행료가 존재한다. 나라에서 도로의 통행료를 인상시킬려고한다. 통행료를 A만큼 인상시켰다면, 모든 도로의 통행료는 A만큼 증가한다. 주언이의 최초 최소통행료와, 세금이 오..
[백준 / BOJ] 2560 짚신벌레
문제 출처 : https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 한 생물학자가 새로 발견된 짚신벌레에 대해 연구하고있다. 짚신벌레는 1. 태어난지 a일째 되는날부터 새로운 개체를 생성한다. 2. 태어난지 b일째 되는날부터 새로운 개체생성을 중지한다(a일부터 b-1일 까지 개체를 생성함) 3. 태어난지 d일째 되는날 죽는다. 수조안에 짚신벌레가 한마리 있다할때, N일 지난후 살아있는 짚신벌레 개체수를 구하는 문제다. 풀이 완전탐색으로 풀경우, d*d*N = O(N*(d^2))이 되..
[백준 / BOJ] 1253 좋다
문제 출처 : www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N개의 수열이 주어진다. 이때, N개의 수 중에서, 어떤 수가 다른 수 두개의 합으로 나타내진다면, 그 수를 좋다 라고한다. 좋은수가 몇개인지 구하는 문제다. (위치가 다르면 값이 같아도 다른 수 이다.) 풀이 완전탐색으로 풀경우 O(N^3)이 되어서 시간초과가 난다. 시간초과를 피하기 위해, 이분탐색으로 풀은 문제다. 로직은 간단한데, 수열 N에서 i번째수를 Ni라 할때, 1. 좋은 수 인지 판단할 수 Ni를 하나 지정한다..