[백준][구현][완전 탐색] 1233 - 주사위

문제

https://www.acmicpc.net/problem/1233

1233번: 주사위

브론즈 2의 난이도 문제 치고 푸는데 생각도 오래 하고 걸리기도 오래 걸린데다 

푸는 방법도 여러 방법으로 나와서 따로 포스팅하게 되었다. 

 

일단 들어가기 앞서 완전 탐색만 알았지 브루트 포스는 처음 들어보는 알고리즘이었는데 

알고보니 둘 다 같은 말이었다.

 

brute = 단순히, 짐승이란 뜻

force = 힘

그냥 짐승처럼 힘만 갖고 밀어붙인다는 뜻으로

 

0000부터 9999까지 가능한 자물쇠가 있을 때 직접 하나씩 바꿔가면 다 해보는 방법을 의미한다. 

 

내 풀이

N = list(map(int, input().split()))
S = []
for x in N:
  arr = [i for i in range(1, x + 1)]
  S.append(arr)

r = 3

result = [0] * r
sum_list = [0] * (sum(N) + 1)

def nPr(L):
  if L == r:
    sum_result = sum(result)
    sum_list[sum_result] += 1
  else:
    for i in range(len(S[L])):
      result[L] = S[L][i]
      nPr(L + 1)
    
nPr(0)
m = max(sum_list)
for i in range(len(sum_list)):
  if sum_list[i] == m:
    print(i)
    break

 

일단 방법은 중복 순열 -> DFS를 활용해 풀었다.

순열 자체가 완전 탐색에 포함되는 영역이기도 하고

 

평소 외워서 사용하는 순열 알고리즘에서 visited를 제외하고 구현하면 중복 순열이 되겠거니 하고

생각만 해왔는데 구현해보니 진짜 매끄럽게 잘 되서 좀 놀랐었다.

 

문제에서 요구하는 해결 방법은 이게 아닌 그냥 for 문 세 개를 써서 푸는 것 같지만..

이 코드의 장점은 주사위가 늘어나더라도 코드 그대로 적용이 가능하단 것?

 

다른 풀이

s1, s2, s3 = map(int, input().split())
counter = {}

for i in range(1, s1 + 1):
  for j in range(1, s2 + 1):
    for k in range(1, s3 + 1):
      summary = i + j + k
      if summary not in counter:
        counter[summary] = 1
      else:
        counter[summary] += 1

max_count = -1
answer = int(1e9)
for key, value in counter.items():
  if max_count < value:
    max_count = value
    answer = key
  elif max_count == value:  # 가장 높은 빈도의 합 중 낮은 합 출력
    answer = min(answer, key)

print(answer)

아마 위 코드대로 푸는게 난이도에 맞는 방법일 것 같은데

말 그대로 머릿속에 떠오르는 그대로 코드로 풀어낸 전형적인 구현 문제 풀이 방법이다.

 

특이사항으로는 counter라는 dict 자료구조를 사용하여 마지막에 답을 얻어낼 때 

max_count와 answer를 각각 -1과 int(ie9)를 세팅한 걸 볼 수 있는데

무한이란 의미로 저렇게 세팅한다는 게 아직까지는 낯설게 느껴져서 나도 쓸 수 있는 상황이 있으면 좀 써봐야 겠다는 생각이 들었다.

 

구현 문제가 쉬운 문제는 엄청 쉽고 나중에 어려워질수록
여러 알고리즘도 같이 쓰면서 코드도 길어져 시간에 대한 압박도 같이 느끼게 하는 까다로운 문제라는데

전체적인 알고리즘 공부가 끝나면 아마 제일 많이 풀어봐야 하는 문제 타입이 되지 않을까 싶다.