PROGRAMMERS 숫자 타자 대회 python
2022년 11월 22일
#algorithm#python#programmers
문제
풀이
- 숫자마다 for문을 돌면서 큐를 갱신함.
- 왼손이 움직이는 경우와, 오른손이 움직이는 경우를 따로 계산.
- 손의 위치가 같은 경우, 비용이 가장 작은 값만 저장.
- 마지막 큐에서 가장 작은 값 리턴.
처음에는 다익스트라로 시도를 했는데, 시간 초과가 났다. 좀 더 고민해보면 이 문제는 그리디로 해결 가능하다. 근데 그리디로 코드를 바꿔도 시간 초과가 났다. move 함수 부분을 원래는 그래프 탐색으로 구현했는데, 간단하게 하드코딩이 가능했다. (x값 차이 + y값 차이)에 움직인 횟수를 더해주면 되는데, 움직인 횟수는 x값 차이와 y값의 차이의 최대값으로 쉽게 구할 수 있다. 제자리에 있는 경우에는 1을 더해주면 된다.
풀이 코드
def solution(numbers):
n = len(numbers)
g = [[1,3],[0,0],[1,0],[2,0],[0,1],[1,1],[2,1],[0,2],[1,2],[2,2]]
dp = [[0 for _ in range(10)] for _ in range(n)]
q = [(0, 0, 4, 6)]
def move(s, w, e):
sx, sy = g[s]
ex, ey = g[e]
if e==w: return 0
return abs(sx-ex)+abs(sy-ey) + max(abs(sx-ex), abs(sy-ey), 1)
ans = 10**8
q1, q2 = [[0, 4, 6]], []
for n in numbers:
n = int(n)
for t, lh, rh in q1:
dt = move(lh, rh, n)
if dt:
for i, q in enumerate(q2):
if (q[1] == n and q[2] == rh) or (q[1] == rh and q[2] == n):
q2[i][0] = min(q2[i][0], t+dt)
break
else: q2.append([t+dt, n, rh])
dt = move(rh, lh, n)
if dt:
for i, q in enumerate(q2):
if (q[1] == n and q[2] == lh) or (q[1] == lh and q[2] == n):
q2[i][0] = min(q2[i][0], t+dt)
break
else: q2.append([t+dt, lh, n])
q1, q2 = q2, []
for q in q1: ans = min(ans, q[0])
return ans관련 글
백준 2927 남극탐험 Python
https://www.acmicpc.net/problem/2927 트리에서 노드 연결, 단일 업데이트, 구간합 쿼리를 수행하는 문제이다. 연결 여부는 union-find로 관리하고, 먼저 모든 연결 쿼리를 수행하여 HLD를 해준다. 이후, 순서대로 쿼리를 처리하면 된다. HLD 과...
BOJ 25910 게이트웨이 정하기 python
문제 게이트웨이 정하기 풀이 비트 연산의 특징을 알아야 풀 수 있는 문제였다. 1. 임의의 노드에서 시작한 결과를 dp에 저장한다. 2. 각 비트를 0인 그룹과, 1인 그룹으로 나눈다.(temp에 1일 경우만 저장) 3. 모든 노드에 대해 헤더와 XOR연산으로 비용을 구한다. 4....
programmers 행렬과 연산 python
문제 행렬과 연산 풀이 표를 적당히 쪼개서 deque로 풀면 된다. 맨 왼쪽 열과 맨 오른쪽 열을 따로 저장해서 deque 2개를 만들고, 각 행의 인덱스를 저장한 deque를 만든다. 연산 시, q, leftq, rightq에 저장된 마지막 인덱스를 맨 앞으로 옮겨준다. 연산 시...