155 원주율 외우기 문제 힌트 부탁드립니다 ㅜㅜ

  • 데구킹
    데구킹

    155번 원주율 외우기
    에 일단 DP로 접근해보려고 몇가지 성질을 봤는데..
    숫자들이 무조건 3자리, 4자리, 5자리 셋중에 하나의 덩이로 묶이는 성질로 재귀식을 짜봤는데요..
    1. S[i][j] : i번째부터 j번째 숫자까지의 수열 ( n 자리 수열이 입력으로 주어진다면 전체수열은 S[1][n])
    2. S[i][j]의 최적해 : A[i]j
    라고 두고
    S[i][j] = min ( A[i][i+2] + S[i+3][j]
    A[i][i+3] + S[i+4][j]
    A[i][i+4] + S[i+5][j] ) 라는 식을 세워봤습니다
    대충 살펴보면 각각의 step 마다 3가지의 선택이 존재하고 하나의 선택을 할때마다 부분문제를 하나씩 만들어내니까..
    bottom up으로 쭉 훑어버리면 O(n²)이 나올것이다!! 라는 생각을 하고
    제한시간을 살펴보니 1000ms 이네요 -_-;
    하루종일 이면지 붙잡고 끄적여봐도 이거이상나오는 아이디어는 생각나질 않고..
    항상 지수공간을 요구하는 문제에서 제한시간까지 조여오면 이렇게 틀어막히네요 ;;
    염치불구하고 힌트 좀 부탁드리겠습니다 (-- a

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    14년 전
2개의 댓글이 있습니다.
  • MiNu
    MiNu

    잠깐 기억나는 대로 말씀드리면...
    생각하신 bottom up 방식으로 하시되 table[i]를 0부터 i-1까지 묶었을 때의 가능한 최소난이도로 정의해 두고 생각해 보세요.
    대략 O(N)에 답을 구하실 수 있을겁니다.


    14년 전 link
  • 데구킹
    데구킹

    회심의 힌트 감사합니다 ㅋㅋ 부분문제를 앞에서부터 자르지 않고 뒤에서부터 자르니 쉽게 풀리네요


    14년 전 link

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