SLENDER ANKLES's 개발블로그

다이나믹 프로그래밍 방법으로 풀 수 있다. 

i+1은 i와 같은 색깔이 아니면서 최소의 비용을 갖아야 한다. 

구조는 [집의번호][색깔]을 사용한다. => dy[i][j]

식 : i까지의 최소 비용 + 해당색깔로 칠했을 때의 비용

을 기본 식으로 사용하여 코딩해나간다.

다음과 같이 코딩해주었다.

경우의 수 문제는 항상 무엇인가 걸림돌이 된다. 

많은 문제를 풀어보면서 경험을 쌓아야하는 것이 좋은 것인지 아니면 접근법에 대한 나름의 규칙을 만들어야 하는 것이 좋은지

잘 모르겠다. 

좌석배치 문제 역시 마찬가지 였다. 

좌석들은 피보나치 수열의 관계를 가진다는 것을 알았다. 

좌석을 배치 받은 사람은 양 옆자리와 원래배정받은 자리에 앉을 수 있는 권한이 있다. 

예제 입출력에서 

9명의 좌석에서 4번좌석과 7번좌석은 고정좌석이라고 했다. 

그렇다면 고정좌석을 경계로 각 그룹들은 피보나치 수열의 관계를 갖는 경우의 수를 갖는다는 것을 알았다.

각 그룹들의 경우의 수는 독립적이므로 서로의 경우의 수를 곱하여 답을 도출 하였다. 

* 홀수번째에 먹는 포션은 포션의 수치만큼 점프력을 증강시킨다.

* 짝수번재에 먹는 포션은 포션의 수치만큼 점프력을 하강시킨다.

이 문제 역시 많은 고민을 해보았지만 딱히 해법이 떠오르지 않았다.

모든문제들을 너무 어렵게만 접근하는 것은 아닌지 모르겠다는 생각을 했다. 

문제는 그리디하게 풀면 풀리는 문제였다. 

꼭지점에서의 포션을 마시면 가장 높이 점프 할 수 있는 요건을 충족시키게 된다. 

- 현재의 지점이 이전과 이후보다 크면 마셔라

- 현재의 지점이 이전과 이후보다 작으면 마셔라

- 연속되는 부분이 나오면 한 점으로 만들어라

(이 부분 때문에 에러가 났지만 입력 받을 때 똑같은 값이 연속으로 들어오게 되면 한 점으로 만들어주게 처리해주니까 오류가 사라졌다)

=> 꼭지점 부분의 포션을 먹으면 된다. 

=> 가장 왼쪽과 가장 오른쪽은 안 마셔야 한다.

(먹을 이유가 없다. 최소지점을 먹는 이유는 다음에 최고 지점이 나타나는 것을 먹기 위해서다)

=> 연속해서 들어오는 입력 값은 하나로 처리하는 것이 문제를 푸는 데 수월하다. 로직에서 같은 값을 처리하는 부분에 대해 예외처리하는 것이 오히려 더 까다롭다.

알파벳 배열에 대한 익덱스를 풀어나가는 것이 관건이었다.

진입한 지점의 알파벳 - 'A'를 배열에 넣어주어 배열의 인덱스를 관리하였다.

dfs를 순회하면서 백트래킹을 사용하였다. dfs함수의 마지막에 알파벳을 거두어 들이면 된다.

오답이 10번 넘게 났는데 이유는 visited배열을 사용해서 였다.

visited배열을 사용하게 되면 제대로 dfs를 순회할 수 없게 된다.

어차피 지나온 경로에 있는 알파벳에는 진입하지 않을 테니까 무한루프에 빠질 이유도 없다.

[틀에박힌 dfs사용으로 인한 오답이었다.]

그래프 문제였다. 

핵심은 이거 였다. 

해당 학생의 키순서의 상대비교를 정확히 알기 위해서는 

내 앞에 있는 학생들과 연결되어있어야 하며

나보다 작은 학생들과도 연결되어야 한다.

dfs한번!

backtracking한번!을 수행하여

visited배열의 갱신되는 부분을 체크하여

모두 방문했으면 이 학생은 상대적인 키순서를 알 수 있는 사람이고

모든 버텍스를 방문하지 못 하는 경우에는 이 학생은 상대적인 키순서를 알 수 없는 사람이다.