문제 풀이 과정 및 느낀점(?)을 공유하고자 한다.
문제 출처

1. 문제설명

• 가로 2칸(고정), 세로 N칸
• 사자들을 우리에 가두고자 함.
  • 가로, 세로 어디든 붙어 있게 배치할 수 없음.
• 배치할 수 있는 경우의 수는?
  • 한 마리도 배치하지 않는 경우도 포함.
  • 출력값은 9901로 나눈 나머지

2. 알고리즘 설계

• n이 입력되었을 때 가장 마지막 n-1번째에 들어올 수 있는 경우는 세 가지
  1. 사자를 배치하지 않음.
  2. 왼쪽에만 사자 배치
  3. 오른쪽에만 사자 배치
• n-2 번째
  • n-1이 비워진 경우
    • 이 경우에만 자기 자신의 케이스까지 올 수 있다.
  • n-1이 왼쪽에 채워진 경우
  • n-1이 오른쪽에 채워진 경우

3. 로직

• 설계했던 부분을 2차원 DP로 구현하면 끝!

int dp[100001][3];
const int MOD = 9901;

dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;

4. 전체 코드

#include <iostream>
using namespace std;

int dp[100001][3];
const int MOD = 9901;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n;
	cin >> n;

	dp[1][0] = dp[1][1] = dp[1][2] = 1;

	for (int i = 2; i <= n; i++) {
		dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
	}

	cout << (dp[n][0] + dp[n][1] + dp[n][2]) % MOD;
	return 0;
}

5. 소감

• 간단한 규칙을 찾은 풀이가 있었다.

  #include <iostream>
  int D[100001]={1,3};
  int main(){
      int N;
      std::cin>>N;
      for(int i=2;i<=N;i++)
          D[i]=(D[i-1]*2+D[i-2])%9901;
      std::cout<<D[N];
  }
  

• 위의 풀이는 간단하다고 생각하지만 좋은 풀이는아니라고 생각한다.
• 블로그 설명에는 케이스의 개수가 이러한 규칙이있다라고 표현되어 있다.
  • 케이스의 개수가 조금 더 복잡한 규칙이었다면찾기 힘들었을 것이다.
• 간단한 DP 문제였지만, 규칙보다는 점화식을위한 접근이 더 중요하다고 느끼게 만든 문제였다.