[그리디 6] 곱하기 혹은 더하기

곱하거나 더하여 가장 큰 수를 만드는 코드를 구현해야 한다. 최대한 많은 곱셈을 사용해야 가장 큰 수를 구현할 수 있기 때문에, 탐욕법을 이용해야 한다. 즉, 그리디 문제이다.

미니 예제 1

1. 문제 설명하기.

S가 02984인 경우이다. 최대한 많은 곱셈을 이용하기 위하여 덧셈을 사용하는 규칙을 찾았다.
S를 하나씩 풀어서 0 이거나 1 또는 총합(result) 이 0인 경우는 더해야 된다고 생각이 들었다.

그래서 조건을 걸어줘서 문제를 풀이하였다.

2. 문제 풀이하기.

# 미니 예제 1 : S=02984 인 경우

S="02984"
result=0

for num in S:
    num=int(num)
    if (num==0) or (num==1) or (result==0):
        result+=num
    else:
        result*=num

print(result)

미니 예제 2

1. 문제 설명하기.

S가 567인 경우이다. 위와 같은 방법으로 풀이하였다.

2. 문제 풀이하기.

# 미니 예제 2 : S=567 인 경우

S="567"
result=0

for num in S:
    num=int(num)
    if (num==0) or (num==1) or (result==0):
        result+=num
    else:
        result*=num

print(result)

최적의 일반화

1. 문제 설명하기.

위와 같은 방법으로 풀이하였다.

2. 문제 풀이하기.

# 최적의 일반화

S=input()
result=0

for num in S:
    num=int(num)
    if (num==0) or (num==1) or (result==0):
        result+=num
    else:
        result*=num

print(result)

3. 책에 나와있는 최적의 일반화

책에서는 나와 비슷하게 풀었다. 하지만 내가 놓친 부분이 있다. 나는 총합이 0인 경우만 덧셈으로 연결하였는데, 총합이 1인 경우에도 덧셈으로 연결해야 한다.

예를 들자면 총합이 1인 경우 4를 더해주거나 곱하여 가장 큰 수를 만들어야 되는 경우가 있다고 하자. 덧셈을 이용하면 1+4=5 이고, 곱셈을 이용하면 1x4=4 이기 때문에 더해주는 것이 더 유리하다.

그래서 조건을 1 이하라고 넣어주었다.

기준	나의 풀이	책의 풀이
반복문	num 그대로 출력하기.	입력 데이터를 이용하여 인덱스를 이용 (1 ~ 끝)하여 출력하기.
조건문	num==0 또는 num==1 또는 result==0	num<=1 또는 result (처음 설정은 S의 첫 번째 숫자로 지정)<=1

# 책에 나와있는 최적의 일반화

S=input()
result=int(S[0]) # 첫 번째 숫자 의미하면서 회차 지날 수록 총합이 된다.

for idx in range(1, len(S)): # 인덱스 (1 ~ 끝까지)
    num=int(S[idx])
    if (num<=1) or (result<=1):
        result+=num
    else:
        result*=num

print(result)