[이코테] 1로 만들기, 개미전사

1로 만들기

정수 표가 주어질 때 정수표에 사용할 수 있는 연산은 다음과 같이 4가지이다.
1. 표가 5로 나누어떨어지면, 5로 나눈다.
2. 표가 3으로 나누어떨어지면，3으로 나눈다.
3. 표가 2로 나누어떨어지면, 2로 나눈다.
4. X 에서 1을 뺀다.
정수 표가 주어졌을 때，연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

첫째 줄에 정수 X7 [ 주어진다. (1 < X < 30,000)
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

입력예시

26

출력예시

3

 

문제풀이

이코테에선 c1~5로 굳이 하지 않고, 미리  c5 조건을 넣어둔 다음 깔끔하게 비교했다. 나는 정답을 궅이 보지 않고 먼저 푸는 스타일이라서, 정답을 보니 아..역시 고수는 보법이 다르구나 싶었다 ㅠㅠ

n = int(input())
d = [0 for _ in range(0, 30001)]
for i in range(0, 30001):
    c1 = 999999
    c2 = 999999
    c3 = 999999
    c4 = 999999
    c5 = 999999
    if(i <= 1):
        c1 = 0
    if (i % 2 == 0):
        c2 =  d[i // 2] + 1
    if (i % 3 == 0):
        c3 =  d[i // 3] + 1
    if (i % 5 == 0):
        c4 =  d[i // 5] + 1
    c5 = d[i - 1] + 1
    d[i] = min(c1,c2,c3,c4,c5)
print(d[n])

 

---

개미전사

개미 전사는 부족한 식량올 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마 을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하끼 위해 서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 

 

개미 전사를 위해 식량창고 N 개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

 

입력예시

1 3 1 5

 

출력예시

8

 

문제풀이

그리디 + dp를 통해 해결할 수 있다.

이게 왜냐면 이전 단계의 값에서 다음 단계로 갈 수 있는 경우의 수가 2개가 있는데, 그걸 비교해서 최대치인 경우가 다음 단계의 최적값이 되기 때문이다.

 

식량창고를 cake[] 최적값 리스트를 dp[] 라고 치자.

 

1까지 선택했을 때의 최적값

cake[0]

0

0

0

 

2까지 선택했을 때의 최적값

1

dp[0], cake[1] 중 큰 값

0

0

 

3까지 선택했을 때의 최적값

1

3

dp[0] + cake[2], dp[1] 중 큰 값

0

 

4까지 선택했을 때의 최적값

1

3

3

dp[1] + cake[3], dp[2] 중 큰 값

 

n = int(input())
cakes = list(map(int,input().split()))
d = [0 for _ in range(0,n)]
mx = 0
# 자기로부터 바로 전 칸 까지만 or 본인 + 한 칸 떨어진 아이 중에서 더 큰 값
for i in range(0,n):
    item = cakes[i]
    if(i <= 1): 
        c1 = cakes[i - 1] if i - 1 >= 0 else 0
        d[i] = max(c1, item)
        mx = max(mx, item)
        continue
    else:
        item = cakes[i]
        c1 = cakes[i - 1] if i - 1 >= 0 else 0
        c2 = cakes[i - 2] if i - 2 >= 0 else 0
        d[i] = max(c1, item + c2)
        mx = max(mx, d[i])

print(mx, d)