codeforces 204 div1 c번 질문드립니다.

  • yeonzzg
    yeonzzg

    문제 링크:
    http://codeforces.com/contest/351/problem/C

    에디토리얼을 봤는데 점화식을 세울때,
    매치되지 않는 '('개수가 n개를 넘어가지 않는다 라는 점을 이용해서 행렬곱 dp로
    해결하던데요.. 저 부분의 성질이 잘 이해가 가질 않네요.

    비둘기집의 원리처럼 생각해볼려 했는데, 얼마든지 매치되지 않는 '('의 개수가 0~n-1을 다 안쓰고도 만들 수 있어서 잘 안되더군요.. 어떤식으로 증명이 될까요?


    10년 전
5개의 댓글이 있습니다.
  • kriii
    kriii

    처음에 모든 괄호를 )로 채웠다고 한 다음에 왼쪽에서 부터 오른쪽으로 가면서 밸런스가 맞지 않게 될때마다 이전에 있던 )를 (로 바꾼다고 생각해 보시면 될거 같습니다.


    10년 전 link
  • yeonzzg
    yeonzzg

    ㅠㅠ 잘모르겠네요 점화식을 뒤집어서 생각해보란 말씀이신가요?


    10년 전 link
  • kriii
    kriii

    이 문제를 O(nm log n)시간에 해결하는 법은 )를 하나씩 추가해보면서 벨런스가 맞지 않게 될때마다 앞에 있는 )중에 (로 바꿔서 잉크가 가장 적게 드는것을 바꾸는 것을 반복하는 것입니다.

    그런데 다시생각해보니 저걸 증명하기는 좀 어려워 보이네요?? ㅜㅜ??

    제가 직관적으로 생각해봤을때 어느 순간부터는 바뀌는 괄호가
    2N을 주기로 같다고 생각되어서 풀었었습니다.


    10년 전 link
  • kriii
    kriii

    http://codeforces.ru/problemset/problem/3/D
    이문제를 한번 풀어보세요


    10년 전 link
  • yeonzzg
    yeonzzg

    아.. 저문제는 일단 그리디하게 ')'로 강제로 채워나가면서 이를 pq로 관리하면서 밸런스가 안맞을때마다 앞의 ')'중 최소코스트가 되는걸 바꿔나가는 식으로 풀리네요.. 확실하게 공식으로 설명은 못해도 항상 최적을 찾아나가겠군요.. 204 c번문제에서는 결국 intended solution이나 d번같은 해법이나 주기성이 중요한 점이 되는데 그게 잘 이해가 안되네요 ㅠ.ㅠ


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.