IT-garden

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍
수학

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
a=[0]+a
dp=[0]*(n+1)
dp[1]=a[1]

for i in range(2,n+1):
    dp[i]=max(a[i], dp[i-1]+a[i])

print(max(dp[1:]))

n개의 정수 , 수열[자리번호]
n = 1 수열[1]
n = 2 수열[1] + 수열[2], 수열[2]
n = 3 수열[1] + 수열[2] + 수열[3], 수열[2] + 수열[3], 수열[3]
n = 4 수열[1] + 수열[2] + 수열[3] + 수열[4], 수열[2] + 수열[3] + 수열[4], 수열[3] + 수열[4], 수열[4]
의 경우의 수가 있습니다.

n = 2를 보면 수열[1] + 수열[2]는 n = 1의 경우에 두 번째 수열을 더하는 경우이고 수열[2]는 두 번째 수열의 값입니다.
따라서 점화식은 해당 n 위치의 값과 이전 dp값에 n 위치의 값을 더한 후 비교하는 경우 2가지로 볼 수 있습니다.
이를 통해 앞에서부터 수열의 각 위치까지 최대값을 구하고 전체 dp에서 최대값을 구하면 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이 됩니다.

백준 알고리즘 1912번 : www.acmicpc.net/problem/1912

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍
수학

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
m=[0]*1000001
m[1]=1
m[2]=2

for i in range(3,n+1):
    m[i]=(m[i-2] + m[i-1]) % 15746

print(m[n])

사용할 수 있는 타일 종류 : '1'과 '00'입니다.

N = 1 이면 1
N = 2 이면 11 00
N = 3 이면 111 100 001
N = 4 이면 1111 1100 1001 0011 0000
N = 5 이면 11111 00111 10011 11001 11100 10000 00001 00100
N = 6 이면 111111 001111 100111 110011 111001 111100 110000 100100 001001 001100 000011 100001 000000

N = 1 이면 1개, N = 2 이면 2개, N = 3 이면 3개, N = 4 이면 5개, N = 5 이면 8개, N = 6 이면 13개

즉, 피보나치 수열의 규칙을 따릅니다.

F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2)

백준 알고리즘 1904번 :www.acmicpc.net/problem/1904 

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력과 출력

알고리즘 분류

수학
중국인의 나머지 정리

정답

e, s, m= map(int, input().split())
c=1

while True:
    if (c-e) % 15 == 0 and (c-s) % 28 == 0 and (c-m) % 19 == 0:
        print(c)
        break
    c += 1

백준 알고리즘 1476번 : https://www.acmicpc.net/problem/1476

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

예제 입력과 출력

알고리즘 분류

수학
이분 탐색

정답

a, b, v=map(int,input().split())

r=(v-b)/(a-b)
print(int(r) if r == int(r) else int(r)+1)

반복문을 사용하니 시간초과가 나옵니다.

v-b를 통해 마지막 날에는 잠자는 것을 고려하지 않습니다.

백준 알고리즘 2869번 : https://www.acmicpc.net/problem/2869