백준: Silver1⑤ - 1303, 1309

</br> 얘네만 다 풀면 골드 5
</br>

1303: 전쟁 - 전투

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

아군과 적군의 위력 구하기

void func(int i, int j){
    d++;
    if( !check[i+1][j] && mmap[i+1][j] == mmap[i][j] ){
        check[i+1][j] = 1;
        func(i+1, j);
    }
    if( !check[i][j+1] && mmap[i][j+1] == mmap[i][j] ){
        check[i][j+1] = 1;
        func(i, j+1);
    }
    if( !check[i-1][j] && mmap[i-1][j] == mmap[i][j] ){
        check[i-1][j] = 1;
        func(i-1, j);
    }
    if( !check[i][j-1] && mmap[i][j-1] == mmap[i][j] ){
        check[i][j-1] = 1;
        func(i, j-1);
    }
}

// in main()
    int W = 0, B = 0;
    for(int i = 1; i < n+1; i++){
        for(int j = 1; j < m+1; j++){
            if( !check[i][j] ){
                d = 0;
                check[i][j] = 1;
                func(i, j);
                if( mmap[i][j] == 0 ) W += pow(d, 2);
                else B += pow(d, 2);
            }
        }
    }


    cout << W << ' ' << B << endl;

진짜 별 거 없고 또 뭉친 거 크기 구하고 제곱해서 더하면 끝
</br>

1309: 동물원

https://www.acmcpc.net/problem/1309

사자 우리 경우의 수 구하기

    dp[1] = 3;
    dp[2] = 7;

    for(int i = 3; i < n+1; i++){
        dp[i] = (2*dp[i-1] % 9901 + dp[i-2] % 9901) % 9901;
    }

    cout << dp[n] << endl;

이렇게 푸는 게 맞는 건지는 모르겠지만??
어째 규칙을 찾으니 dp[i] = 2*dp[i-1] + dp[i-2]가 나와서 해 보니 맞았다.
중간 중간 모듈러도 해 주면 되고
</br>

그래도 일단 좀 더 생각해 보니, 사자가 왼쪽 오른쪽 둘 중 하나만 들어가거나 없어야 한다. 둘 다 없는 걸 0, 왼쪽만을 1, 오른쪽만을 2라 하고, 한 줄씩 더해진다고 생각하면

dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]
ex)
..  ..  ..
..  ..  ..
00  10  01

마찬가지로 다른 경우들도

dp[i][1] = dp[i-1][0] + dp[i-1][2]
ex)
..  ..
..  ..
00  01
10  10

dp[i][2] = dp[i-1][0] + dp[i-1][1]

그리고 얘네를 다 더한 dp[i][0] + dp[i][1] + dp[i][2]가 답이 되겠다.
</br>

그런데… 그럼 저 규칙이랑은 무슨 연관이 있을까 봤는데

dp[i] = dp[i][0] + dp[i][1] + dp[i][2]
      = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]
        + dp[i-1][0] + dp[i-1][2]
        + dp[i-1][0] + dp[i-1][1]
      = 3*dp[i-1][0] + 2*dp[i-1][2] + 2*dp[i-1][2]
      = 2*dp[i-1] + dp[i-1][0]

까지는 나온다.
그럼 dp[i-1][0] == dp[i-2]가 맞는 지를 보면

dp[i-1][0] == dp[i-2]
dp[i][0] == dp[i-1]
         == dp[i-1][0] + dp[i-1][1] + dp[i-1][2]

해서 맞네~~

처음엔 운빨 비스무리로 풀긴 했는데 아무튼 이런 dp 식을 세울 수 있는 문제였다
</br>

---

골드 5가 되었다~~ 805점이다
실버 5에서 시작한 지 6일 째다
이제 골드 5 문제를 풀지, 아니면 실버들 좀 더 풀지 생각해 봐야 겠다
</br>