2행을 가지는 원형으로 이어진 순열에서 특정값(N,W)을 바탕으로 두 값을 하나로 묶을 수 있는 조건(W)을 제시받아 순열 원소숫자의 최소값(소대)을 구하는 문제입니다.
2학기 기말고사때 멋모르고 풀어보려다가 DP개념을 모르고 헤딩해서 정말 많은 시간을 보냈네요..
풀다보니까 DP에 대한 개념도 어느정도 잡히고
처음으로 테스트케이스?를 다량으로 출력시키는 문제를 풀어봤습니다..
한 테스트케이스가 끝나면 답안을 출력시키는 형태인줄 알고 왜 틀리고있었나 고통받고있었지만
t1
~~~~~
ans1
t2
~~~
ans2
이런 형식으로 출력을 했는데 아니더군요..(출력조건은 한행에 한 답만 출력하라고 되어있음)
드디어 해결을 했습니다..
처음 접근법으로는 막대한 재귀함수(브루트포스?)를 사용해서 모든 경우의 수를 계산한 후 다시 재귀하여 또 계산하여서(DP개념없이 푸는 최악의 예시법을 생각하시면 됩니다) 하다가 안되겠다 싶어서 순열간에 L R 이라는 조건을 생각해서 원순열 내부의 순열은 수직으로 우선적으로 계산을 해주고 LR가능여부를 다른 배열에 기록을 해서 그 기록을 바탕으로 최선의 값을 구해보려고 했습니다.
하지만 수직값을 우선으로 한 것이 발목을 잡더군요..
이렇게 보면 DP라는 개념이 시간복잡도도 엄청 줄여주고 식을 세우는데 있어서 매우 좋은 개념이다 싶었습니다.
rudcks5562 2년 전 10
2행을 가지는 원형으로 이어진 순열에서 특정값(N,W)을 바탕으로 두 값을 하나로 묶을 수 있는 조건(W)을 제시받아 순열 원소숫자의 최소값(소대)을 구하는 문제입니다.
2학기 기말고사때 멋모르고 풀어보려다가 DP개념을 모르고 헤딩해서 정말 많은 시간을 보냈네요..
풀다보니까 DP에 대한 개념도 어느정도 잡히고
처음으로 테스트케이스?를 다량으로 출력시키는 문제를 풀어봤습니다..
한 테스트케이스가 끝나면 답안을 출력시키는 형태인줄 알고 왜 틀리고있었나 고통받고있었지만
t1
~~~~~
ans1
t2
~~~
ans2
이런 형식으로 출력을 했는데 아니더군요..(출력조건은 한행에 한 답만 출력하라고 되어있음)
드디어 해결을 했습니다..
처음 접근법으로는 막대한 재귀함수(브루트포스?)를 사용해서 모든 경우의 수를 계산한 후 다시 재귀하여 또 계산하여서(DP개념없이 푸는 최악의 예시법을 생각하시면 됩니다) 하다가 안되겠다 싶어서 순열간에 L R 이라는 조건을 생각해서 원순열 내부의 순열은 수직으로 우선적으로 계산을 해주고 LR가능여부를 다른 배열에 기록을 해서 그 기록을 바탕으로 최선의 값을 구해보려고 했습니다.
하지만 수직값을 우선으로 한 것이 발목을 잡더군요..
이렇게 보면 DP라는 개념이 시간복잡도도 엄청 줄여주고 식을 세우는데 있어서 매우 좋은 개념이다 싶었습니다.