[백준 1463번] 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

1. 1로 만들기 위해서는 먼저 3으로 나눌 수 있으면 나누고 3으로 못 나눌시에 2로 나누고 나눌 수 없는 경우에 1로 빼는게 1로 만드는 가장 빠른 방법으로 생각함.
2. 하지만 10의 경우 2를 먼저 나누는 경우가 아닌 1을 빼고 계산하는 경우가 제일 빨리 1로 만들 수 있음

   2로 먼저 나누는 경우: 10 -> 5 -> 4 -> 2 -> 1
   1을 먼저 뺀 경우 : 10 -> 9 -> 3 -> 1

3. BOTTOM-UP 방식을 이용하여 작은 문제부터 시작해서 큰 문제로 확장하여 해결

   숫자 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))

python 코드

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()

---

[백준 9095번] 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

풀이

1. 1, 2, 3의 합으로만 나타나기 때문에 4 이후 부터는 이전에 계산한 방법의 수를 불러와서 더할 수 있습니다.

   4의 경우의 수 :

   • 1 + 3의 경우의 수
   • 2 + 2의 경우의 수
   • 3 + 1의 경우의 수

     n의 경우의 수 = n-1의 경우의 수 + n-2의 경우의 수 + n-3의 경우의 수

python 코드

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])

---

[백준 1912번] 연속합

문제

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

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

풀이

1. 입력받은 연속의 값을 배열로 선언
2. 입력받은 값과 같은 크기의 배열을 선언
3. 자기 자신과 자신 앞의 수를 더했을 때의 수 중 더 큰 수를 저장
4. 저장된 값중에 가장 큰 수를 출력

python 코드

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))