문제 링크

문제 설명

< < < < 가 주어질때, 1 < 2 < 3 < 4 < 5 이렇게 숫자를 넣을수 있다. < > < > 가 주어지면, 1 < 5 > 4 > 5 > 4 를 넣을 수 있다. 바로 앞뒤만 비교하면 된다. <<>< 같은 S가 주어지고, 그 사이사이에 숫자를 넣었을때 그 숫자들의 합이 최소가 되도록 했을때, 그 합은?

예시

[input]
<>>

[output]
3

[input]
<>>><<><<<<<>>><

[output]
28

사고의 흐름

1하고 2만으로 만들 수 있는거는 1 < 2 > 1 < 2 > 1 이렇게

뭔가,, > 이 모양의 개수에 따라서 필요한 숫자의 범위가 달라질것같다.

먼저 >의 개수를,,,아니야, 방향성이 중요하네. S를 루프돌면서 그 방향성을 체크하는거야. <가 몇개인지, >가 몇개인지가 중요하지 않을까? 아니면 시작점을 1이나 2로 잡아…안되지. 중간에 > >> 이런게 있으면 안되지. 다시말해서 이거는 S를 루프 돌리면서 답을 구할수는 없고, 미리 S를 돌려서 사전정보를 파악한다음에 그걸가지고 다음 추측을 해봐야한다. 배열을 만들어서 그 연속된 구간들은 그룹핑해서 저장해놓을까? 왜냐하면 사실 아니야.

그래프로 생각을 해보자. 무조건 차이는 1씩 두고, 아 0이되는 지점만 피하면 될것같은데… 아 0이 되는 지점을 찾아보자. 거기에 답이 있을것같아. 맞네 그루핑해서 봐야하네.
> > > < < > < > > > < < < 이렇게 되어있으면

> > > < < > < > > > < < < 이렇게 나눌 수 있고 근데 지금 올라가는게 있어도 뒤에거를 고려 하지 않으면 안되. 뒤에서 쫘라락 내려가버리면 어쩔거야? 내려가는놈을 조심해야되. 내려가는놈 사이사이에 있는 것들을 계산해줘야해. 내려가는놈 사이에 있는거는, 올라가는게 있어도 되니까. 그거는 효력이 있잖아. 지금같은 경우도 >>> >>> 를 포함해서 그 사이에 총 7번이 내려가잖아. 그러니까, 마지막 >>>까지 했을때 -1보다는 크려면 7 – 3(<가 3개는 있으니까)에서 시작해야한다는거야. 뒤에 <<< 이거는 지금 의미가 없어. 즉 4에서 시작해야지.

아! 아니면, 일단 0에서 시작해서 쭉쭉쭉 그려놓고, 0이되는 지점에 선을 그맨 밑에있는놈이 0이 되지 않도록 전체를 위로 올려도 될것같은데?

앗!! 근데 생각해보니까 이 모두를 움직이는건 너무 손해야. 부분만 움직여서 최소화 할 수 있잖아..

그러면, 하락선에 있는 놈들만 제일작은놈의 절대값만큼 더해주면 되는건가? 하기야, 올라가는놈한테 굳이 더 힘을 줄 필요는 없지. 근데 또 아무 하락선이나 위로 올리면 안될것 같은데,,,

그러면 루프를 돌때 pick를 저장해 놓자. 올라가다가 내려가는부분이 있으면 pick로 저장해 놓는거야. 그러다가 음수를 발견하면 이젠 오르막길을 예의주시해서 봐야지. 0밑에있는그래프에서는 pick를 무시하고, 그 음수로 내려가는 그 라인의 피크와 다시 물 밖으로 나오고 있는 그 라인의 pick 사이에 있는 값들에 모두 가장 작은 음수의 절대값만큼 더해주면 되겠네.

그럼 pick를 항상 저장하고 있어야 하나? => 그렇지. 근데 걱정되는건 저렇게 물에 빠지는 놈들이 많으면 어떡하지,,,

저렇게 겹칠때는, pick부분이 물밑에 빠진놈과 합했을때 0보다 크면 안더하는걸로 하자..

그래 이렇게 하는것도 맞긴 한데, 구현이 너무 어려워, 저 피크 부분을 찾는게 어렵다. 이 방법은 포기하고 다른 방법을 생각해보자.

모범답안

여기를 누르면 보입니다
def answer(S) :
  n = len(S)
  h = [0] * (n + 1)
  for i in range(n) :
    if S[i] == '<' :
      h[i+1] = max(h[i+1], h[i] + 1)
  for i in range(n, 0, -1) :
    if S[i-1] == '>' :
      h[i-1] = max(h[i-1], h[i]+1)
  print(h)
  return sum(h)

S = input()
print(answer(S))