[프로그래머스][Search] 주사위게임(201012)

 

 

1. 문제 설명

 

문제 설명

XX 모바일 보드게임은 같은 크기의 칸으로 구분된 직선 모양의 게임 보드와 특별한 주사위 3개를 사용해서 진행합니다. 주사위는 각각 1부터 S1, S2, S3까지의 숫자 중 하나가 나오며, 3개의 주사위를 동시에 굴려 나온 숫자의 합만큼 캐릭터를 이동시킵니다. 게임 보드의 몇몇 칸에는 몬스터가 있으므로, 캐릭터는 도착한 칸에서 몬스터를 만나게 될 수도 있습니다.
다음은 S1 = 2, S2 = 3, S3 = 4인 경우의 예시입니다.

 

 

위 그림에서 별은 캐릭터이며, 붉은 사각형은 몬스터입니다. 캐릭터는 1번 칸에 있습니다. 주사위를 던져 나온 숫자가 1, 1, 2라면 캐릭터는 총 4칸을 이동하여 5번째 칸에 도착해 몬스터를 만납니다. 반면에 주사위를 던져 나온 숫자가 2, 2, 1이라면 총 5칸을 이동한 캐릭터는 6번째 칸에 도착해 몬스터를 만나지 않습니다. 위 예시에서 주사위를 한 번만 굴렸을 때, 주사위 눈의 합만큼 이동해 도착한 칸에서 몬스터를 만나지 않을 확률은 0.5입니다.

 

몬스터의 위치를 담고 있는 배열 monster와 각 주사위에서 나올 수 있는 최대 숫자 S1, S2, S3가 매개변수로 주어질 때, 1번 칸에 위치한 캐릭터가 주사위를 한 번만 굴려 나온 눈금의 합만큼 이동해서 도착한 칸에 몬스터가 없을 확률을 return 하도록 solution 함수를 완성해 주세요. 단, return 값은 몬스터를 만나지 않을 확률에 1000을 곱한 후 소수부는 버리고 정수 부분만 return 하세요.

 

제한사항

• monster는 몬스터의 위치를 담은 배열이며 길이(몬스터의 개수)는 1 이상 99 이하입니다.
• monster의 각 원소는 현재 몬스터의 위치를 나타내며, 모든 몬스터의 위치는 2 이상 100 이하의 자연수입니다.
• 같은 위치의 몬스터가 여러 번 중복해서 주어지지 않으며, 한 칸에는 한 마리의 몬스터만 있습니다.
• 각 주사위를 던져 나올 수 있는 수의 최댓값 S1, S2, S3는 다음과 같습니다.
  • 2 ≤ S1 ≤ 30, 2 ≤ S2 ≤ 30, 2 ≤ S3 ≤ 40, S1, S2, S3는 자연수
• 몬스터를 만나지 않을 확률에 1000을 곱한 후 소수부는 버리고 정수 부분만 int형으로 return 해주세요.

---

입출력 예

monsterS1S2S3result

[4,9,5,8]	2	3	4	500
[4,9,5,8]	2	3	3	555

입출력 예 설명

 

입출력 예 #1
몬스터의 위치는 문제에 주어진 예시와 같습니다.
몬스터가 없는 칸에 도착할 확률은 1/2로 0.5이며 1000을 곱한 후 소수부를 버리면 500이 됩니다.

 

입출력 예 #2
몬스터의 위치는 문제에 주어진 예시와 같습니다.
몬스터가 없는 칸에 도착할 확률은 5/9로 0.55555... 이며 1000을 곱한 후 소수부를 버리면 555가 됩니다.

 

 

 

 

2. 풀이 

1) 완전 탐색 

모든 주사위 경우의 수 리스트에 담은뒤에 몬스터 등장 카운트 세기 (아주 단순)

 

def solution(monster, S1, S2, S3):
    
    first_list = list(range(2,S1+2)) # 2부터 시작하는 이유는 출발점이 1이니까, 

    second_list = []
    for two_num in range(1,S2+1):
        for one_num in first_list:
            second_list.append(one_num + two_num)
    
    total_list = []
    total_len = 0
    for last_num in range(1,S3+1):
        for onetwo_num in second_list:
            chk_dict[onetwo_num + last_num] = 0 
            total_list.append(onetwo_num + last_num)
            total_len +=1 
            
    mon_chk = 0
    for one_mon in monster:
        mon_chk += total_list.count(one_mon)

    return int(((total_len - mon_chk) / total_len) *1000)
        

 

분명 쉽게 푸는 치트키나 점화식이 있을거라 생각했는데,, 완탐으로도 런타임에러 없이 풀렸다. 

 

 

다른 풀이를 살펴보니

 

from itertools import product

def solution(monster, S1, S2, S3):
    board_num = S1 + S2 + S3 + 1 # 도착할 수 있는 최대 칸 번호
    
    # 몬스터를 만날 수 있는 칸 이동 수
    monster_in = set([(m - 1) for m in monster if m <= board_num])
    
    # 주사위 모든 경우의 수
    s1_list = list(range(1, S1 + 1))
    s2_list = list(range(1, S2 + 1))
    s3_list = list(range(1, S3 + 1))
    temp = [s1_list, s2_list, s3_list]
    total_case_list = product(*temp) # 두 개 이상의 리스트에서 모든 조합
    
    # 몬스터를 만날 수 있는 경우의 수
    case_num = 0
    for case in total_case_list:
        if sum(case) in monster_in:
            case_num += 1
    
    return int((1 - case_num / S1 / S2 / S3) * 1000)

크게 다르지 않지만 그래도 모든 경우의 수를 만드는 걸 product 를 쓰셔서 더 깔끔하다 

 

 

 

 

3. 정리

아직 어떤 유형의 문제를 접했을 때 완탐인지 그리디인지 뭐인지 감이 잘 안온다 

brenden.tistory.com/10

[알고리즘] 완전탐색

완탐 유형을 정리해놓으셨는데 시간날때 쭉보면 좋을 듯 !