[백준/Algorithm] 1463, 9095, 1912
[백준 1463번] 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
풀이
- 1로 만들기 위해서는 먼저 3으로 나눌 수 있으면 나누고 3으로 못 나눌시에 2로 나누고 나눌 수 없는 경우에 1로 빼는게 1로 만드는 가장 빠른 방법으로 생각함.
- 하지만 10의 경우 2를 먼저 나누는 경우가 아닌 1을 빼고 계산하는 경우가 제일 빨리 1로 만들 수 있음
2로 먼저 나누는 경우: 10 -> 5 -> 4 -> 2 -> 1
1을 먼저 뺀 경우 : 10 -> 9 -> 3 -> 1 - 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, 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이 정답이 된다.
풀이
- 입력받은 연속의 값을 배열로 선언
- 입력받은 값과 같은 크기의 배열을 선언
- 자기 자신과 자신 앞의 수를 더했을 때의 수 중 더 큰 수를 저장
- 저장된 값중에 가장 큰 수를 출력
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))
Author And Source
이 문제에 관하여([백준/Algorithm] 1463, 9095, 1912), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jenny87879/백준Algorithm-1463-9095-1912저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)