BOJ:鉄棒[107799]
3605 ワード
1.質問
何本もの鉄棒がレーザーで切らなければならない.効率的に動作するために、鉄棒を下から上へ重ね、上から垂直にレーザーを発射し、鉄棒を切断します.鉄棒とレーザーの配置は以下の条件を満たす:
鉄の棒は自分より長い鉄の棒にしか置けません.鉄棒を別の鉄棒の上に置くと、端点が重ならないように完全に含まれるように配置されます.
各鉄棒を切断するレーザー光は少なくとも1つ存在する.
レーザーはいかなる鉄棒の両端にも重ならない.
次の図は、上記の条件を満たす例を示しています.水平に描かれた太い実線は鉄棒で、点はレーザーの位置で、垂直に描かれた破線の矢印はレーザーの発射方向です.
これらのレーザーと鉄棒の配置は、括弧で左から右に順に表すことができます.
レーザーは、左かっこと右かっこの隣接するペア「()」として表されます.また、すべての「()」はレーザー光を表す必要があります.
鉄棒の左端は左かっこ「(」,右端は右かっこ「)」で表される.
前例のカッコは図に表されます.
鉄棒はレーザで数枚に切断され、上記の例では、最上位の2本の鉄棒はそれぞれ3枚と2枚に切断され、このようにして与えられた鉄棒は全部で17枚に切断された.
鉄棒とレーザーの配置を表す括弧が与えられた場合、切断された鉄棒片の総数を求めるプログラムを作成してください.
ソース:https://www.acmicpc.net/problem/10799
2.アイデア
3.コード
minebracket = list(input())
stack = []
result = 0
for i in range(len(bracket)):
if bracket[i] == '(':
stack.append(i)
else:
if bracket[i-1] == '(': #()가 되면 (를 pop, 스택에 들어있는 ( 수만큼 값을 더해준다.
stack.pop()
result += len(stack)
else:
stack.pop()
result += 1 # 막대기의 끝부분을 더해준다
print(result)
Reference
この問題について(BOJ:鉄棒[107799]), 我々は、より多くの情報をここで見つけました
https://velog.io/@onejh96__/BOJ-쇠막대기-10799
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
bracket = list(input())
stack = []
result = 0
for i in range(len(bracket)):
if bracket[i] == '(':
stack.append(i)
else:
if bracket[i-1] == '(': #()가 되면 (를 pop, 스택에 들어있는 ( 수만큼 값을 더해준다.
stack.pop()
result += len(stack)
else:
stack.pop()
result += 1 # 막대기의 끝부분을 더해준다
print(result)
Reference
この問題について(BOJ:鉄棒[107799]), 我々は、より多くの情報をここで見つけました https://velog.io/@onejh96__/BOJ-쇠막대기-10799テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol