[그리디] 02.곱하기 혹은 더하기 (유형별 기출문제, 이것이 코딩테스트다 with 파이썬)

그리디 개념

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기
• 다양한 알고리즘에 두루 사용    # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘

빈출유형

거스름돈 문제

• 거슬러 줘야 할 동전의 최소 개수 찾는 문제
• 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업

1이 될 때까지

• N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산
• 최대한 많이 나누기가 문제 해결 아이디어

 

문제

 

해설

• 일반적으로 특정 두 수의 연산에서 '+'보다는 'x'가 더 값 크게 만듦
• 단, 0인 경우에는 '+' 연산이 효율적
• 즉, 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우 합, 두 수 모두 2 이상인 경우 곱

 

풀이

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    elseL
        result *= num
        
print(result)

 

해석

변수 : 숫자 문자열 data, 최대 연산값 result

 

1. 숫자 문자열 data 입력받기

2. 최대 연산값 result 정의    # 문자형으로 더해지지 않도록, int로 바꿔줌

---------------------------- 반복문 : 숫자 문자열 data 길이 만큼 ----------------------------

3. 두 수의 상태 점검

ㄴ 둘 중 하나라도 0 : +연산

ㄴ 둘 다 0이 아님 : x 연산

-----------------------------------------------------------------------------------------------------------

4. 출력