dokrsky   7달 전

지금 다이나믹으로 접근해보고 싶은데, 도저히 안떠오르네요 ㅜㅜ

1 2 3 4 -> 3 1 1 0 으로 만들기 위해서

2 2 3 4 -> 3 2 3 4 -> 3 1 2 3 -> 3 1 1 2 -> 3 1 1 1 -> 3 1 1 0 해서 총 6번인건 알겠는데, 이걸 dp로 접근하기가 힘듭니다 ㅠㅠ

도와주세요 ! ㅠ

alohajihwan   7달 전

dp로 접근하려면 먼저 반복되는 경우가 언제 발생하는지 봐야 합니다.

이 문제를 풀기 위해서 알아야할 핵심은 각각의 index에서 (출발지 - 도착지) 가 같은 부호 이면 같은 그룹이 된다는 것입니다.

그룹 각각을  처리할 때 이제 dp가 사용 됩니다. 처리하는 방법은 그룹 내에서 가장 작은 값(절대값) 을 정하고 그만큼을 그룹 전체에 빼준 다음 

가장 작은 값을 제외한 그룹에서 다시 그 과정을 거치는 것 입니다.

alohajihwan   7달 전

예를 들어 

5

1 1 1 1 1

5 3 1 3 5

가 주어지면 일단 모든 index는 -로 부호가 같아 하나의 그룹입니다. 이제 이 그룹을 처리할 때 차이 값이 가장 작은 index를 찾습니다. 

이 경우는 3번째 경우이지요. 그 다음 3번째 index를 제외한 첫번째~두번째, 4번째~5번째 그룹을 다시 위의 과정을 거치게 합니다.

결국 하나의 그룹내에서 dp 반복이 생겨 dp로 풀 수 있는 것입니다. 

dokrsky   7달 전

alohajihwan 님 답변감사합니다!!

밑의 코드는 제가 작성한 건데, 틀렸습니다 가 나옵니다 ㅠㅠ

어디가 잘못된걸까요? 

alohajihwan   7달 전

// 만약 -3, -5, -1 이라면 가장 큰 연속 된 그룹내에선 5번을 누르면 됨 

이 가정이 잘못 됬습니다. 만약 인풋이 

5

1 1 1 1 1

5 3 2 3 2 로 주어지면

일단 3번째 부호를 맞춰줘서 2 2 2 2 2가 됩니다(1) 그다음 이제 3번째 수를 건들면 안되기 때문에 1~2번째 4~5번째 그룹으로 나눕니다

그다음 2 2

           5 3

           2  2

           5 3

두개의 그룹으로 나눠서 생각해야 하기 때문에 답이 7 나옵니다.

결국 이 문제를 풀기 위해서는 그룹을 나눠서 생각하는 분할정복(DP)를 사용해야 합니다.

dokrsky   7달 전

alohajihwan님 감사합니다! 제출했더니 맞았습니다가 뜨네요 ㅎㅎ 정말 감사드립니다!!!!

grands   3달 전

위에 테케

5
1 1 1 1 1
5 3 2 3 2

답이 5아닌가요?

댓글을 작성하려면 로그인해야 합니다.