정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
2로 먼저 나누는 경우: 10 -> 5 -> 4 -> 2 -> 1
1을 먼저 뺀 경우 : 10 -> 9 -> 3 -> 1
숫자 1: 0번의 연산 필요
숫자 2: 1번의 연산 필요(2/2)
숫자 3: 1번의 연산 필요(3/3)
숫자 4: 2번의 연산 필요(4/2 또는 4-1) +연산 1추가
숫자 5: 3번의 연산 필요(5-1) + 숫자 4의 연산 추가
숫자 6: 2번의 연산 필요(6/2 또는 6/3) + 연산 1 추가
..
숫자 9: 2번의 연산 필요(9/3) + 숫자 3의 연산 추가
숫자 10: 3번의 연산 필요(10-1) + 숫자 9의 연산 추가n번째 숫자의 연산 횟수
f(n) = 1 + min(f(n/3)+f(n/2)+f(n-1))
def solve():
n = int(input())
arr = [0,0,1,1,2]
for i in range(5, n+1):
one, two, three = math.inf, math.inf, arr[i-1]
if i % 3 == 0 :
one = arr[i//3]
if i % 2 == 0 :
two = arr[i//2]
arr.append(1+min(one, two, three))
print(arr[n])
solve()
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
4의 경우의 수 :
- 1 + 3의 경우의 수
- 2 + 2의 경우의 수
- 3 + 1의 경우의 수
n의 경우의 수 = n-1의 경우의 수 + n-2의 경우의 수 + n-3의 경우의 수
test_case = int(input())
arr = [0 for _ in range(11)]
for i in range(test_case):
n = int(input())
arr[1] = 1
arr[2] = 2
arr[3] = 4
for i in range(4, n+1):
arr[i] = arr[i-3] + arr[i-2] + arr[i-1]
print(arr[n])
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
count = int(input())
arr = list(map(int, input().split()))
ans = [0] * count
ans[0] = arr[0]
for i in range(1, count):
ans[i] = max(arr[i], arr[i]+ans[i-1])
print(max(ans))