문제 풀이 질문입니다.

  • dkwkekzz
    dkwkekzz

    안녕하세요.

    문제 풀이에 관한 질문인데요. 2가지가 있습니다.

    첫번째는 특정 문제에 관한 질문입니다.

    문제

    꼭 문제의 답이 아니어도 힌트가 있다면 꼭 얻고싶습니다.

    해당 조건을 만족하면서 분해할 수 있는 최소값을 만족하는 경우의 수를 구하는 문제입니다.
    무슨 문제인가요? 아무리 봐도 특정 규칙같은 것은 없어서 DP문제라고 생각했습니다.
    결론은 안 풀립니다. 왜안풀릴까? 모든 경우를 순회하는 자체가 안됩니다. 생각해보면 일단 적절히 인자를 정해서 다음과 같은 함수를 정의했습니다.
    index에서 남은 개수가 n이면서 s개의 간선을 끊었을 때, 가능한 경우의 수
    인자가 3개이므로 메모이제이션이 터집니다. 3가지 인자를 순회하는 방식으로는 시간상으로도 안된다고 생각했습니다.
    다른 함수 정의나 방법이 필요한데 떠오르지 않습니다.

    힌트좀 주시면 감사하겠습니다.

    두번째는 문제 해결 방법에 관한 질문인데요.

    그리 오랜시간을 알고리즘에 투자한 것은 아니지만, 어느 수준 이상의 문제를 푸는게 어려워보입니다. 무슨 수를 써서라도 푸는 편이지만 시간이 너무 오래걸립니다. 그래서 많은 문제를 푸는 것도 장애가 됩니다. 정답을 볼 수가 없으니까요.

    다른 분들은 어떻게 훈련하시는지 궁금합니다. 인터넷 커뮤니티도 백준이나 여기 알고스팟정도 알고 있는데 쉬운 문제에 대해서는 답변이 빠르게 올라오는 것 같은데 난이도가 약간 높으면 답변이 아예 없습니다. 왜그런지는 잘 모르겠는데 사정상 주변에서 정보를 얻기가 어려워 여기에라도 질문을 올려봅니다. 생각하시기에 효율적이거나 적절한, 혹은 주변의 정황, 대부분에서 하는 방법 등 알려주시면 감사하겠습니다.

    정리해보면,

    1. 위의 문제에 대한 힌트

    2. 알고리즘 문제 풀이 훈련 방법

    답변해주신다면 정말 감사하겠습니다^^~~~~~


    5년 전
1개의 댓글이 있습니다.
  • Arine
    Arine

    코더즈하이 공식 사이트?에 솔루션이 공개되어 있습니다.


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