[백준 11058] 크리보드, C++
https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V 를 눌러 27개를 출력할 수 있다. www.acmicpc.net 본 문제는 크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대 개수를 구하는 문제로 문제의 조건은 다음과 같다. 화면에 A를 출력한다. Ctrl-A: 화면을 전체 선택한다 Ctrl-C: 전체 선택한 ..
2020. 2. 16.
[백준 15486] 퇴사 2, C++
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 본 문제는 퇴사와 조건은 똑같다. 차이는 입력의 크기가 퇴사는 15, 퇴사 2는 1,500,000으로 퇴사 소스코드로 퇴사 2를 풀 수 없다. 퇴사할 때까지 최대로 많은 이익을 얻으려면 퇴사 전까지 많은 이득을 얻어야 하기 때문에 큰 문제를 작은 문제로 해결할 수 있다. 그리고 계산의 반복이 있다. 따라서, DP로 문제 해결이 가능하다. 이 문제는 선택 여부에 따라 ..
2020. 2. 13.
[백준 1939] 중량제한, C++
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 www.acmicpc.net 본 문제는 두 개의 섬에 다리를 세워 물품을 수송하려고 한다. 그런데 각각의 다리마다 중량 제한이 있다. 중량 제한을 초과하면 다리를 통과..
2020. 2. 11.
[백준 1790] 수 이어 쓰기 2, C++
https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 본 문제는 1 ~ n 까지의 수를 이어서 썼을 때 길이를 구하고 k의 위치의 값을 출력하는 문제다. n의 최대값이 매우 크기 때문에 실제로 값을 구해서 찾는 것은 불가능 하다. 따라서, k와 인접한 위치를 찾아서 출력하는 방식을 이용해야 한다. 이때, 이분 탐색을 이용하면 빠르게 답을 구할 수 있다. 예를 들어 n = 20 일 때, 우선 n까지의 길이가 k보다 짧을 경우를 예외처리 한다. 1 ~ 9 까지의 길이를 구하고 10 ~..
2020. 2. 5.