[Python] 백준 1339 단어수학, 백준 20055 컨베이어 벨트 위의 로봇

1. 문제 - 백준 1339 단어수학

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

 

💡 알고리즘: 그리디

예시 2인 사례를 보면,

입력: 
2
GCF
ACDEB

출력:
99437

 

A -> 9, C -> 8, D -> 7 .. 이런식으로 자리수가 가장 큰 알파벳 순서대로 큰 수를 대입한 경우가 곧 그 수의 합을 최대로 만드는 것이고,

자릿수가 큰 순서대로 큰 수를 고르는 것이 곧 최적의 답을 보장하므로, (상황마다 가장 큰 수를 선택함) 그리디 알고리즘이라고 생각할 수 있다.

 

✅ 풀이

from collections import defaultdict

dic = defaultdict(int)   # 각 알파벳의 자리수를 저장할 딕셔너리
n = int(input())

for _ in range(n):
  word = input()
  _len = len(word)

  # 1)
  for i, w in enumerate(word):
    dic[w] += 10 ** (_len-i-1)

# 2)
dic = sorted(dic.items(), key=lambda x:x[1], reverse=True)
answer = 0

for i, (k, v) in enumerate(dic):
  answer += v * (9-i)

print(answer)

 

1) 마찬가지로 예시 2를 가지고 식을 세워보자.

입력: 
2
GCF
ACDEB

출력:
99437

 

A는 10000, C는 1010, D는 100, E, 10, B는 1, G는 100 F는 1일 것이다.

[GCF]

_len = 3

G = 10 ** (3 - 0 - 1) = 10 ** 2 = 100

C = 10 ** (3 - 1 - 1) = 10 ** 1 =  10

F = 10 ** (3 - 2 - 1) = 10 ** 0 = 1

 

[ACDEB]

_len = 5

A = 10 ** (5 - 0 - 1) = 10 ** 4 = 10000 ....

 

이 규칙을 식으로 세우면 10 ** (_len - i - 1) 이다.

 

2) 자릿수가 큰 알파벳 순서대로 9, 8, 7, 6... 수를 매칭해야하므로 자릿수가 큰 순서대로 딕셔너리를 정렬한다.

그 다음 9, 8, 7, 6... 을 차례대로 곱해서 더하면 해당 합이 정답이다.

 

이를 일반화하면 딕셔너리의 value * (9-i)가 된다.

 

2. 문제 - 백준 20055 컨베이어 벨트 위의 로봇 (삼성SW역량테스트 기출)

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

 

💡 알고리즘: 시뮬레이션, 구현

 

✅ 풀이

n, k = map(int, input().split())
# 내구도가 0인 칸의 갯수가 k개 이상이라면 멈춤
conveyor = list(map(int, input().split()))
robots = [0] * 2*n
step = 1

while True:
  # 한칸 회전한다.
  conveyor.insert(0, conveyor.pop())
  robots.insert(0, robots.pop())

  # 언제든지 로봇이 내리는 위치에 도달하면 내린다.
  robots[n-1] = 0

  # 가장 먼저 벨트에 올라가있는 로봇 -> 역순 탐색
  for i in range(2*n-1, -1, -1):
    if robots[i] == 1:
      ni = (i+1) % (2*n - 1)   # 다음 위치를 2*n-1로 나누는 이유는 2*n-1 다음은 0이기 때문이다.
      if robots[ni] == 0 and conveyor[ni] >= 1:   # 이동하려는 칸에 로봇이 없고, 그 칸의 내구도가 1 이상
        robots[i] = 0   # 로봇 이동
        robots[ni] = 1
        conveyor[ni] -= 1

  # 언제든지 로봇이 내리는 위치에 도달하면 내린다.
  robots[n-1] = 0

  if conveyor[0] > 0:  # 올리는 위치의 내구도가 0이 아니면 로봇 올리기
    conveyor[0] -= 1
    robots[0] = 1

  count = 0
  for c in conveyor:
    if c == 0:
      count += 1

  if count >= k:
    break

  step += 1

print(step)

 

- 벨트와 로봇을 각각의 배열로 만든다.

- 배열로 만든다고 했을 때, 한 칸 회전하는 것은 맨 끝의 원소가 맨 앞에 위치하는 것과 같다.

  # 한칸 회전한다.
  conveyor.insert(0, conveyor.pop())
  robots.insert(0, robots.pop())

- 나머지는 문제에 있는대로 구현해주면 되는데, 주의할 점은 "언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다" 는 것이다.
즉, 회전하거나 로봇이 이동할 때 모두 로봇을 내림처리 (robot[n-1] = 0) 해주어야한다.