BOJ-10799 쇠막대기
https://www.acmicpc.net/problem/10799
문제 소개
여러 개의 쇠막대기를 레이저로 절단할 때 잘려진 쇠막대기 조각의 총 개수를 구한다.
쇠막대기와 레이저의 배치는 아래 조건을 따른다.
쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
레이저는 “()”으로 표현되며, 쇠막대기의 왼쪽 끝과 오른쪽 끝은 각각 “(“와 “)”으로 표현된다.
문제 풀이
입력으로 주어진 괄호 표현에서 먼저 레이저를 판별하기 위해, 입력받은 문자열 s에 replace()를 사용하였다.
그리고 이어질 풀이에서 마지막 레이저에 도달했는지 여부가 필요하므로, 레이저의 개수도 얻어서 저장한다.
아래는 풀이에 사용할 변수들이다.
bar : 양쪽 레이저에서 동시에 잘리는 막대의 개수
acc : 한쪽 레이저에서만 잘리는 막대의 개수
cur : 현재 겹쳐진 막대의 개수
l_visited : 검사한 레이저의 개수
l_cnt : 전체 레이저의 개수
문제의 조건에 따라 각 쇠막대기를 자르는 레이저는 적어도 하나 존재하므로, 두 레이저 사이에 있는 막대기는 존재하지 않는다.
즉, 인접한 두 레이저가 있을 때, 양쪽 레이저에서 동시에 잘리는 막대의 개수와 한쪽 레이저에서만 잘리는 막대의 개수를 더하면 레이저로 잘려서 생기는 조각의 개수를 얻을 수 있다.
이제 s를 순차적으로 탐색하며 각 레이저의 사이마다 bar와 acc를 계산하여 그 둘을 더한 값을 result에 누적시킨다면 생기는 조각의 총 개수를 얻을 수 있다.
bar는 인접한 두 레이저 사이에서 cur의 최솟값이다.
acc는 s를 보았을 때 인접한 두 레이저 사이에 위치한 괄호의 개수이다.
레이저로 잘려서 생긴 좌측의 조각을 result에 누적시키도록 구현하였기 때문에, 마지막 레이저인 경우에는 우측에 남은 조각의 개수를 result에 더해주어야 한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from sys import stdin
input = lambda: stdin.readline().rstrip()
s = input()
# 레이저 판별
s = s.replace("()", "L")
l_cnt = s.count("L")
# result : 정답
# bar : 양쪽 레이저에서 동시에 잘리는 막대의 개수
# acc : 레이저 사이의 괄호 개수
# cur : 현재 겹쳐진 막대의 개수
# l_visited : 검사한 레이저의 개수
result, bar, acc, cur, l_visited = 0, 0, 0, 0, 0
# 레이저를 만날 때마다 bar + acc를 result에 누적시킨다
for i in range(len(s)):
# 레이저인 경우
if s[i] == "L":
result += bar + acc
# 레이저로 자르고 나면 bar와 acc를 다시 초기화
bar = cur
acc = 0
l_visited += 1
# 마지막 레이저라면 오른쪽 자투리를 더한다
if l_visited == l_cnt:
result += bar
break
# 괄호인 경우
else:
acc += 1
# 겹쳐진 막대의 개수 갱신
if s[i] == "(":
cur += 1
else:
cur -= 1
# bar 갱신
if cur < bar:
bar = cur
print(result)