[백준 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.
[백준 10816] 숫자 카드 2, C++
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,00 www.acmicpc.net 본 문제는 n개의 숫자 카드를 보유하고 있을 때, 해당 숫자가 적혀있는 숫자 카드의 개수를 m번 출력하는 문제다. 이분 탐색을 ..
2020. 2. 5.
[백준 17089] 세 친구, C++
https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친구라는 것을 의미한다. 사람은 1번부터 N번까지 번호가 매겨져 있다. 같은 친구 관계가 두 번 이상 주어지는 경우는 없다. www.acmicpc.net 본 문제는 n명의 사람 중 a, b, c 세 명을 선택한다. a, b, c 세 명 다 친구 일 경우 각각 친구의 수의 합을 구한다. 단, a의 친구 수를 계산할 때, b와 c는 빼고 계산해야 하고, b의 친구 수를 계산할 때는 a와 c..
2020. 2. 4.
[백준 17088] 등차수열 변환, C++
https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다. 수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가 www.acmicpc.net 본 문제는 주어진 수열을 등차수열로 변환하는 문제로 각각의 수에 연산을 최대 한 번 적용할 수 있고, 연산은 1을 더하거나 빼는..
2020. 2. 2.
