AndroidTeacher

www.acmicpc.net/problem/2156

문제 설명

포도주가 ( a, b, c, d, e, f ) 식으로 일렬로 나열되어 있다. a, b, c, d...는 포도주의 용량을 뜻한다.

연속으로 3잔 이상을 마실 수 없을 때, 최대로 마실 수 있는 포도주의 용량을 구하면 된다.

풀이 과정

6잔의 포도주 ( 6, 10, 13, 9, 8, 1 ) 가 있다고 생각해보자.

마지막 포도주를 마실지 말지를 결정하는 상황이라고 할 때,

내가 9와 8을 이미 마셨다면 1은 마실 수 없으며,

13과 9을 마신경우와 13과 8을 마신 경우에는 1을 마실 수 있다.

이 경우 중에서, 가장 많이 마실 수 있는 상황을 고르면 되는 것이다.

즉, 현재 포도주를 마실 지 말지를 결정 할 때는

① 현재 포도주와 이전 포도주를 마시고 전전 포두주는 마시지 않는다. ( wine[i]+wine[i-1]+d[i-3] )

② 현재 포도주와 전전 포도주를 마시고 이전 포도주는 마시지 않는다. ( wine[i]+d[i-2] )

③ 현재 포도주를 마시지 않는다. ( d[i-1] )

이 세 가지 경우로 나눌 수 있다.

이 때, 3번케이스의 경우 d[i-2]+wine[i-1] 로 표기하지 않은 이유는

d[i-1]에 해당 케이스를 포함한 최댓값이 저장되어 있기 때문이다.

포도잔이 3잔 이하인 경우에는 인덱스에러를 방지하기 위해 예외처리를 먼저 해주면 코드가 완성된다.

n = int(input())

wine = []

for i in range(n):
    wine.append(int(input()))

d = [0]*n

d[0] = wine[0]
if n > 1:
    d[1] = wine[0]+wine[1]

if n > 2:
    d[2] = max(wine[2]+wine[1], wine[2]+wine[0], d[1])

for i in range(3, n):
    d[i] = max(d[i-1], d[i-3]+wine[i-1]+wine[i], d[i-2]+wine[i])

print(d[n-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1003

문제 설명

자세한 문제 설명은 위의 링크에 나와있습니다!

피보나치 함수란, N번째 수의 값이 N-1 + N-2 의 값이 되는 함수입니다.

fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다.

풀이 과정

이 문제를 문제에서 주어진 C++코드를 그대로 이용해 0과 1의 횟수를 구하려고 하면 시간초과가 난다.

왜냐하면 f(10)을 호출했다고 가정할 때, f(10) = f(9) + f(8)이 되기 때문에 

f(9)와 f(8)을 한번씩 호출하게 되는데,

f(9) = f(8)+f(7) 이므로 f(9)가 f(8)을 한번 더 호출 하게 된다.

이런 식으로, 중복되어 호출되는 경우가 많이 생기기 때문에 이 방식을 이용하면 안된다.

한번 구한 수는, 다시 구하지 않고 값을 저장하여 이용할 수 있도록

DP(Dynamic Programming)개념을 이용하면 된다.

d라는 리스트를 2차원으로 만들어 d[x][0]에는 0이 호출된 횟수, d[x][1]에는 1이 호출된 횟수를 저장하였다.

0일 경우는 1, 0

1일 경우는 0,1 이 고정이므로 이 두개 값만 고정값으로 두고

3부터는 이전의 값을 이용해 구하도록 구현하였다.

t = int(input())

for i in range(t):
    n = int(input())

    if n == 0:
        print("1 0")
    elif n == 1:
        print("0 1")

    else:
        d = [[0] * 2 for _ in range(n + 1)]
        d[0][0] = 1
        d[1][1] = 1
        d[2] = [1, 1]
        for j in range(3, n + 1):
            d[j][0] = d[j - 1][0] + d[j - 2][0]
            d[j][1] = d[j - 1][1] + d[j - 2][1]

        print("%d %d" % (d[n][0], d[n][1]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1463

문제 설명

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

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

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

풀이 과정

이 문제는, 전의 결과를 다음 결과에 이용하게 되는. 점화식을 활용한 DP 문제이다.

X = 10인 경우, 10 -> 9 -> 3 -> 1  과정을 거쳐 1이 되게 되는데

9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며

3의 경우에는 3 -> 1의 과정을 거친다.

즉, 10을 구할 때는 9의 결과를,

9를 구할 때는 3의 결과를 이용한다.

앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다.

일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에

dp[i] = dp[i-1] + 1을 통해 횟수를 +1 추가 해준다.

그리고나서, dp[i]가 2 와 3으로 나누어 떨어지는 경우에는

1을 빼는 것 보다 나누어 떨어지는게 훨씬 이득이기 때문에

min(dp[i], dp[i//2]+1)을 통해 최소값을 선택하면 된다.

n = int(input())

dp = [0] * (n+1)

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

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !