[BOJ] 24392 영재의 징검다리

---

3달정도 알고리즘에서 플젝하느라 알고리즘에서 거의 손을 떼고 있었더니 감이 많이 떨어졌다.

같이 플젝하던 팀원이 자기도 감이 떨어졌다면서 추천해준 문제인데 정말 화가 난다...

진짜... 오랜만에 알고리즘 푸는 사람들이 풀어야할 문제이자 너무 화가나는 문제다.

---

1. 문제

https://www.acmicpc.net/problem/24392

 

2. 문제 분석

처음엔 DFS로 풀었다.

시간 오버일 건 알고있었지만 오랜만에 DFS연습겸 + 사실 난 틀려야 제약조건이 눈에 들어온다...

 

역시나 시간초과.

어떻게할까 고민했다. 집 지붕 색칠문제 같은 걸로 두세번 풀어본 유형인 건 알겠는데 방법이 뭐였는지 생각이 안난다.

그리고 1000000007로 나머지 연산을 하란 것도 걸린다.

그래도 우선은 시간초과부터 해결하자.

 

3. 풀이

무슨 알고리즘을 써야할 진 모르겠지만 메모이제이션을 써야겠단 생각까진 해냈다.

아래처럼 해당 칸까지 올 수 있는 경우의 수를 더하는 방식으로 했다.

 

4. 문제점

1000000007로 나머지 연산이 문제였다.

자꾸 1%에서 틀려서 뭐가 문제인가 한참을 고민했다.

1000000007라는 숫자를 보자마자 int형을 벗어난다는걸 알았으면서 정작 배열과 합산용 변수를 long으로 선언할 생각은 못했다. 멍충멍충(대충 이용진 터키즈 짤)

 

5. 비교

갓 나온 문제인지 아직 푼 사람이 많이 없어서 2등 먹긴 했는데 1등 대체 뭐야...무서워...

구경간다...