buzz

문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 해설 누적합을 저장할 리스트를 만들고 0 ~ i까지의 누적합을 계산해 저장한다. a~b까지의 구간 합은 b까지의 누적합과 a까지의 누적합을 뺀 것이기 때문에 누적합만 계산해서 넣어두면 쉽게 풀 수 있다. 리스트에 0을 미리 넣어두면 인덱스를 헷갈리지 않고 풀 수 있다. 코드 -파이썬 #백준 11659(구간 합 구하기 4) import sys input = sys.std..

문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 해설 처음에는 밑의 주석처리 된 시간 초과 코드 처럼 풀면 쉽게 해결될 거라고 생각했다. 그치만 이중 반복문을 쓰면 시간복잡도가 O(n^2)이 되어 시간 초과가 난다. 이 문제는 투포인터 문제로 리스트의 가장 처음(0)과 가장 마지막(n-1)을 각각 포인터로 설정해 위치를 옮겨가면서 원하는 값을 구하면 된다. left 위치와 right ..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 해설 방법의 수를 계산해보면 1, 2, 4, 7, 13, 24가 나오는데 이걸 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]인 것을 알 수 있다. 처음엔 5까지만 방법의 수를 세보고 dp[i]의 방법의 수는 그 이전 수들의 방법의 수의 총합이라고 생각했는데 6까지 세어보니 완전 아니었다.. 완전 헛짓거리 하고 있었다. 코드 -파이썬 #백준 9095(1, 2, 3 더하기) t = int(input()) dp = [0] * 11 dp[1] = 1 dp[2] = 2 dp[..

문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 해설 이 문제는 dp문제로 규칙만 찾으면 쉽게 풀 수 있다. 처음엔 2*5까지 직접 정리해보고 dp[i] = dp[i-1] + dp[i-2] + (2*(i-2)-1) 인 줄 알았다. 그러나 백준 예제입력2만 해봐도 이게 아니란 걸 알 수 있다. 규칙 찾는데 약간 헤맸지만 자세히 보면 dp[i] = dp[i-1] + (dp[i-2]*2)규칙을 찾을 수 있다. dp[i-1]과 dp[i-2]를 알아내려면 최소한 dp[1], d..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 해설 이 문제는 dp 문제이다. 위 그림을 보면 n = (n-1) + (n-2) 임을 알 수 있다. 결국 dp[1]과 dp[2]의 개수만 미리 넣어놓는다면 그 후 dp[n]의 개수들은 쉽게 구할 수 있다. 다만, dp 배열을 초기화할 때 dp = [0] * (1001)이 아니라 dp = [0] * (n + 1)을 해주면 런타임 에러가 뜨는데 왜 뜨는지 모르겠다.. 코드 -파이썬 #백준 11726(2*n 타일링) ..

문제 www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 해설 물이 새는 곳을 막기 위해서는 앞뒤로 총 1만큼의 간격이 더 필요하다. 시작위치보다 물 새는 위치가 더 뒤에 있을 때 막을 수 있다. 일단 구멍 하나를 막으면, 테이프 길이 - 1(앞뒤 0.5) 위치에 있는 구멍까지 다 막을 수 있다. 그렇기 때문에 시작 위치만 마지막으로 막은 구멍으로 옮겨주면 간단하게 해결할 수 있다. 코드 -파이썬 #백준 1449(수리공 항승) n, l = map..

문제 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 해설 이 문제는 다음과 같은 2가지 과정을 통해 카드 합체를 하는 문제이다. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y) 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다. 위와 같은 과정을 m번 거쳤을 때 모든 카드의 합이 최소가 되게 하는 것이 목표이므로, 매번 고르는 x번 카드와 y번 카드는 ..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 해설 이 문제는 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구해야 하는 문제이다. 앞 사람의 시간이 계속해서 더해져 나가기 때문에 앞 사람이 가장 적은 시간만을 사용해야 전체 시간의 합이 최소가 될 것이다. 푸는 방법은 다양하겠지만, 나는 오름차순 정렬을 이용해 풀었다. 정렬 후에는 이중 for문을 이용한다면 쉽게 풀 수 있다. 코드 -파이썬 #백준 11399(ATM) n = int(input()) #사람 수..