본문 바로가기
728x90

수열

 (4)
[백준] 11660번 구간 합 구하기 5 [Python] - 다이나믹, 누적 합 N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 문제. $(x, y)$는 x행 y열을 의미한다. 1차원 수열의 구간 합 문제 https://savvy0402.tistory.com/216 위 문제와 비슷하지만 이번에는 2차원 수열의 구간 합을 구하는 문제라고 보면 된다. 더보기 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. $(x1, y1)$부터 $(x2, y2)$까지 합을 구하는 프로그램을 작성하시오. $(x, y)$는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 $(2, 2)$부터 $(3, 4)$까지 합을 구하면 3..
[백준] 11659번 구간 합 구하기 4 [Python] - 누적 합 N 개의 수가 주어졌을 때, 1 ≤ i ≤ j ≤ N인 i번째 수부터 j번째 수까지 합을 구하는 문제 i, j 순서쌍은 M번 주어짐 더보기 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N https://www.acmicpc.net/problem/11659 수열 $A_{n}..
[백준] 3060번 욕심쟁이 돼지 [Python] - 등비수열 매일 N만큼의 사료로 돼지를 먹일 수 있다. N과 첫 날 돼지들이 먹은 양이 주어진다. 돼지들은 매일 전날 자신이 먹었던 양에 양 옆 돼지들과 맞은 편의 돼지가 먹었던 양까지 더해서 먹고 싶어한다. 돼지들의 요구를 들어줄 수 없게 되는 날을 구하는 문제 더보기 문제 유명한 농부 박현수는 돼지 6마리를 키우고 있다. 그는 하루에 한 번씩 돼지에게 맛있는 밥을 준다. 돼지는 원형 식탁에 앉아서 식사를 한다. 현수의 돼지들은 기억력이 뛰어나기 때문에 전 날 자신의 양쪽과 맞은편에 앉았던 돼지가 먹었던 양을 기억하고 있다. 또, 욕심도 많기 때문에, 그 만큼의 양을 추가하여 식사를 하기를 원한다. 예를 들어, 현수가 1번부터 6번까지 돼지에게 각각 3, 2, 7, 1, 5, 4만큼 밥을 주었다면, 2번 돼지는 ..
[백준] 1904번 01타일 [Python] - 피보나치 수열 00과 1로 N자리수 이진수를 만드는 경우의 수 구하는 문제 $($경우의수를 15746로 나눈 나머지 출력$)$ 더보기 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. $($01..

티스토리툴바