Python | 정다면체

crystal·2021년 9월 5일
0

Algorithm

목록 보기
7/8

정다면체

1. 문제 🧐

두 개의 정 N면체와 정 M면체의 두 개의 주사위를 던져서 나올 수 있는 눈의 합 중 가장 확률이 높은 숫자를 출력하는 프로그램을 작성하세요.
정답이 여러 개일 경우 오름차순으로 출력합니다.

2. 입력

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

4 6


3. 출력

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

5 6 7


4. 문제 풀이 핵심 point 🔍

솔직히 나는 섹션 2에서 가장 어려운 문제가 정다면체 문제라고 생각한다.
푸는데 제일 오래 걸렸다. 🤣🤣 그리고 너무 중구난방으로 풀어서 핵심포인트 짚기도 어렵다. 같은 원리로 풀긴했는데 내 코드 보다는 모범 답안을 보는게 깔끔할 듯 하다.

입력
4 6
👉 정 4면체와 정6면체의 합을 구해야한다.

아래는 정4면체와 정6면체의 합을 나타내는 테이블이다.

4 / 6123456
1234567
2345678
3456789
45678910

이 리스트는 합의 카운팅을 저장하는 리스트이다.

인덱스012345678910
리스트00123444321

👉 인덱스는 정사면체와 정육면체의 합을 나타낸다. 0 ~ n+m 까지 len(n+m+1)
👉 리스트는 정사면체와 정육면체 합을 카운팅한다. => 카운팅한 값이 최대값 구할 때 쓰임

위와 같은 원리로 풀면 된다. 나는 리스트를 3개나 만들어서 복잡하게 풀었는데 모범답안은 리스트의 인덱스를 두 수의 합으로 쓰고, 인덱스(두 수의 합)에 해당하는 값에 카운팅해놨다. 리스트 하나만 써도 된다니 훨씬 간결하고 깔끔한 것 같다.

5. 코드 💻

1) 내 풀이

import sys
# sys.stdin=open("input.txt","r")
N, M = map(int, input().split())


sum = [] #주사위 눈의 합을 담을 리스트 
sum_cnt_list = [0]*(N+M-1) #주사위 눈의 합 카운팅할 거 담을 리스트
# print(idx_list)


# 1단계 : sum 리스트에 주사위 눈의 합을 넣어 준다.
for i in range(1, N+1) :
    for j in range(1, M+1):
        s = i + j
        sum.append(s)

# 2단계 : sum2리스트에 중복제거한 주사위 합의 값을 넣는다. (set이용)
sum2 = list(set(sum)) # 중복제거한 sum

# 3단계 : sum2만큼 돌리고 중복제거하지 않은 sum과 비교해서 같으면 카운팅을 1로 올려준다.
# sum_cnt_list 에 합의 확률이 들어가게 된다.
for idx, n in enumerate(sum2):
    for s in sum:
        if n == s:
            sum_cnt_list[idx] += 1

# print(sum)
# print(sum2)
# print(sum_cnt_list)

max = 0 #최대값 구할 때 제일 작은 값
max_list = []
midx = 0


# sum_cnt_list 인덱스를 이용하는 게 핵심
# sum_cnt_list와 sum2의 인덱스는 같음
# 4단계 : sum2에서 가장 확률이 높은 숫자 구하기 (최대값 구하기)
for idx, i in enumerate(sum_cnt_list):
    if max < i : #최대값 구하기
        # print(max, '<', i)
        max = i   # sum_cnt_list와 최대값을 저장
        midx = idx # midx는 idx_list의 최대값의 인덱스 저장
    elif max == i :
        max_list.append(sum2[idx])

max_list.append(sum2[midx])
max_list.sort()  #오름차순으로 정렬 
# print('max:',max,'midx:',midx)
# print(max_list)

for i in max_list:
    print(i, end=' ')

2) 모범 풀이

import sys 
sys.stdin=open("input.txt","r")
n, m = map(int, input().split())

cnt=[0]*(n+m+1)
max=-2147000000

# 1단계 두 수의 합 카운팅  , 여기서 인덱스가 두수의 합이 된다.
for i in range(1, n+1): # 1~n까지 
	for j in range(1, m+1):# 1~m까지
    	cnt[i+j]+=1 

# 2단계 : 두 수의 합 카운팅한 값 중에 최대값 구하기 
for i in range(n+m+1): # 0 ~ 10까지 (인덱스=두수의합)
	if cnt[i] > max: 
    	max=cnt[i] # 카운팅 최대값

# 3단계 : 두수의 합 최대값들 출력
for i in range(n+m+1): # 0 ~ 10까지 (인덱스=두수의합)
	if cnt[i] == max: # 카운팅 최대값이면 
    	print(i, end=' ') 두 수의합 최대값 출력





1단계 : 두 수의 합 카운팅

코드

for i in range(1, n+1): # 1~n까지 
	for j in range(1, m+1):# 1~m까지
    	cnt[i+j]+=1 

👉 코드를 실행하면 위의 그림과 같이 리스트에 두 수의 합 카운팅 값이 저장된다.





출처 : 한국정보올림피아드
profile
어제보다 더 나은 오늘의 내가 되자 ✧ʕ̢̣̣̣̣̩̩̩̩·͡˔·ོɁ̡̣̣̣̣̩̩̩̩✧ 

0개의 댓글