[백준 1337] 올바른 배열 (C++)
https://www.acmicpc.net/problem/1337문제올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정..
2025. 3. 26.
[백준 14246] K보다 큰 구간 (C++)
https://www.acmicpc.net/problem/14246문제 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j] (i≤j)의 합이 k보다 큰 모든 쌍 (i,j)의 개수를 출력하시오.입력첫째 줄에는 자연수의 개수 n이 주어진다. (1 ≤ n ≤ 100000)다음 줄에는 자연수 n개가 주어진다. 자연수는 100,000보다 크지 않다.그 다음 줄에는 자연수 k가 주어진다. (1 ≤ k ≤ 1,000,000,000) 출력특정 구간 [i,j]의 합이 k보다 큰 모든 쌍 (i,j)의 개수를 출력하시오. 문제 풀이투 포인터 문제. 주어진 수가 모두 자연수이므로 [i, j]가 k보다 크다면 j보다 큰 모든 수 l에 대해 [i, l]이 k보다 크다. 이를 이용하여 투포인터를 사용하여 i(=투포인..
2024. 12. 19.
[백준 30804] 과일 탕후루 (C++)
https://www.acmicpc.net/problem/30804문제은하는 긴 막대에 𝑁개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 𝑆1, 𝑆2, ⋯, 𝑆𝑁번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 𝑎개, 뒤에서 𝑏개의 과일을 빼면 𝑆𝑎+1, 𝑆𝑎+2, ⋯, 𝑆𝑁−𝑏−1, 𝑆𝑁−𝑏번 과일, 총 𝑁−(𝑎+𝑏)개가 꽂혀있는 탕후루가 됩니다. (0 ≤ 𝑎,𝑏; 𝑎 + ?..
2024. 8. 11.