- back과 front를 더하면 limit인 100보다 작으므로 front도 오른쪽으로 한 칸 움직이자.
- back을 왼쪽으로 한 칸 움직이자.
3.
- back과 front를 더하면 limit인 100보다 작으므로 front도 오른쪽으로 한 칸 움직이자.
- back을 왼쪽으로 한 칸 움직이자. (back이 front보다 앞으로 가게 되므로 반복문이 종료된다.)
코드
def solution(people, limit):
answer = 0
people = sorted(people)
front = 0
back = len(people)-1
while front < back:
answer += 1
if people[front] + people[back] <= limit:
front += 1
back -= 1
return answer
(4-1) data[3]에는 비교대상이 없으므로 dy, queue 리스트의 변화가 없습니다.
(5) q에 있는 (8,3)은 이미 dy[3]보다 크므로, 비교/갱신을 진행하지 않고 꺼냅니다.
(6) 답을 리턴합니다.
- 1000000을 제외하고 가장 큰 값은 최종 감염시간을 나타냅니다 : 6
- 1000000을 제외한 값의 개수는 감염된 컴퓨터의 수를 나타냅니다 : 3
dy
문제풀며 작성한 구상도
문제 풀면서 작성했던 구상도입니다. 혹시 위의 설명으로 부족하신 분은 참고해서 봐주세요
코드
import sys
import heapq
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")
numTestcase = int(input())
for _ in range(numTestcase):
n, d, c = map(int, input().split()) # n : 컴퓨터 수, d : 의존성 수, c : 감염원
data = [[] for _ in range(n+1)] # '인덱스'는 의존받는 대상(b), '값'은 [(x초 후 감염, 의존하는 대상(a))]
for _ in range(d):
a, b, s = map(int, input().split()) # 감염 방향: b -> a, s초 후 감염
data[b].append((s, a))
# 다익스트라 알고리즘
dy = [100000000] * (n+1) # 몇 초 후에 감염되는지 저장
dy[c] = 0 # 감염원(c)은 0초 후에 감염
q = [(0, c)]
while q:
timePassed, infectedCp = heapq.heappop(q)
if dy[infectedCp] < timePassed:
continue
for s, a in data[infectedCp]:
if dy[a] > s + timePassed:
dy[a] = s + timePassed
heapq.heappush(q, (s+timePassed, a))
time = -1
nCp = 0
for i in range(1, n+1):
if dy[i] != 100000000:
time = max(time, dy[i])
nCp += 1
print(nCp, time)
- 문제 조건에서 알파벳을 A,B,C 순서만이 아니고 A,Z,Y와 같이 역순으로도 셀 수 있다고 했다.
따라서 최소 CNT가 되기 위해 13을 기준으로 한다.
2. 옆으로 이동
반복문을 돌며, 각 자리에서 좌측 또는 오른쪽으로 갔을 때 최소의 움직임 횟수를 구한다.
- 0번 인덱스는 중앙에 위치한다.
- 파란색 동그라미를 시작으로 0번 인덱스의 왼쪽 방향에 위치한다.
- 0번 인덱스 오른쪽 방향에는 빨간색동그라미까지의 인덱스 값이 위치된다.
- 0번 인덱스의 값을 기준으로, 왼쪽 끝까지 탐색하고 오른쪽 끝까지 위치했을 때 움직임 횟수를 구한다.
- 0번 인덱스의 값을 기준으로, 오른쪽 끝까지 탐색하고 왼쪽 끝까지 위치했을 때 움직임 횟수를 구한다.
- 왼쪽과 오른쪽 중 더 짧은 움직임으로 답을 갱신한다. (비교될 움직임 횟수의 초기 값은 전체길이 - 1)
코드
import sys
def solution(name):
s = name
r = list()
# 알파벳 올리기/내리기
for c in s:
print(ord(c))
r.append(ord(c) - 65)
cnt = 0
for i in r:
if i <= 13:
cnt += i
else:
cnt += (26 - i)
# 옆으로 이동
min_movement = len(r) - 1
for red in range(len(r)):
blue = red + 1
while blue < len(r) and r[blue] == 0:
blue += 1
center = len(r) + red - blue
LR, RL = red, len(r) - blue
min_movement = min(min_movement, center + min(LR, RL))
return min_movement + cnt
if __name__ == '__main__':
R = input()
print(solution(R))
