[알고리즘] 정다면체

(문제) 정다면체

---

두 개의 정 N면체와 정 M면체의 두 개의 주사위를 던져서 나올 수 있는 눈의 합 중 가장 확률이 높은 숫자를 출력하는 프로그램을 작성하세요.

정답이 여러 개일 경우 오름차순으로 출력합니다.

입력설명

첫 번째 줄에는 자연수 N과 M이 주어집니다. N과 M은 4, 6, 8, 12, 20 중의 하나입니다.

출력설명

첫 번째 줄에 답을 출력합니다.

테스트케이스

입력예제	출력예제
4 6	5 6 7
8 8	9
12 20	13 14 15 16 17 18 19 20 21
8 12	9 10 11 12 13
6 20	7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

---

해결방법

방법 1 (반복문 이용)

1. 정다면체1 과 정다면체2가 더해서 만들어 질 수 있는 값의 경우를 key 값으로 놓고 반복이 몇번이 일어나는 지를 value로 생각한다.

2. 그 해시 테이블에서 value가 가장 큰 값을 찾아서 그 value 값을 가지고 있는 key들을 출력 한다.

방법 2 (순차적인 효과 이용)

1. 규칙은 절대값(정다면체 1의 최대 경우의 수 - 정다면체 2의 최대 경우의 수) + 1

2. 기준 작은 정다면체의 최대 경우의 수 + 1 부터 ~ 규칙 + small 까지의 경우들 출력

---

방법 코드 1

# 순차적 특징 이용하지 않고 알고리즘을 이용
n, m = map(int, input().split())

_sum = {}

# 값 해시로 사용
# 첫번째 정다면체
for i in range(1, n+1):
    # 두번째 정다면체
    for j in range(1, m+1):
        # 각각 한번 씩 더하기
        # 만약 더한 값이 해쉬 테이블에 있을 경우
        if _sum.get(i+j):
            # 값을 1 더한다
            _sum[i+j] += 1
        else:
            # 값을 1로 초기화 한다
            _sum[i+j] = 1

# 만약 _sum 의 해시테이블의 key에서
for key in _sum.keys():
    # value 중 가장 큰 값이 해당 key에 대응하는 value일 경우 출력
    if _sum[key] == max([k for k in _sum.values()]):
        print(key, end=' ')

방법 코드 2

# 순차적인 특징 이용
n, m = map(int, input().split())

# 규칙은 절대값(정다면체 1의 최대 경우의 수 - 정다면체 2의 최대 경우의 수) + 1
rule = abs(n-m) + 1

# 기준은 작은 정다면체
small = min([n, m])

# 작은 정다면체 최대 경우의 수 + 1 부터 ~ 규칙 + small 까지의 경우들
k = list(range(small+1, small+rule+1))

# 값 출력
print(*k)