백준: Class 3 ⑤ - 9461, 10026, 11399

</br> 클래스 3 계속 계속
</br>

9461: 파도반 수열

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

방법 1.

    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
    for(int i = 6; i < 101; i++){
        dp[i] = dp[i-1] + dp[i-5];
    }
    while( t-- ){
        int n;
        cin >> n;

        cout << dp[n] << '\n';
    }

이것도 dp
dp[i] = dp[i-1] + dp[i-5]라는 규칙이 있더라
dp를 출력해 보니 int 범위를 넘어 가더라. 그래서 long long으로 선언했다.
</br>

방법 2.

dp[i] = dp[i-2] + dp[i-3]

그런데 찾아 보니 이런 식도 있다 헉 어떻게 된 거지 둘이 같은 걸까

dp[i]   = dp[i-1] + dp[i-5] = dp[i-2] + dp[i-3]
dp[i-1] = dp[i-2] + dp[i-6]

// dp[i-1] = dp[i-2] + dp[i-6] 대입
dp[i-2] + dp[i-6] + dp[i-5] = dp[i-2] + dp[i-3]

dp[i-3] = dp[i-5] + dp[i-6]
dp[i] = dp[i-2] + dp[i-3]

대충 두 식이 맞다고 가정하고 식을 막 돌리니까 맞다고 나온다
</br>

10026: 적록색약

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

void bfs(){
    while( q.size() ){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx < 0 || n <= nx || ny < 0 || n <= ny ) continue;
            if( visited[nx][ny] == 0 && mmap[nx][ny] == mmap[x][y] ){
                q.push(make_pair(nx, ny));
                visited[nx][ny] = cnt;
            }
        }
    }
}

void bfs2(){
    while( q.size() ){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if( nx < 0 || n <= nx || ny < 0 || n <= ny ) continue;
            if( visited[nx][ny] == 0 && (mmap[nx][ny] == mmap[x][y]
                || (mmap[nx][ny] == 'R' && mmap[x][y] == 'G')
                || (mmap[nx][ny] == 'G' && mmap[x][y] == 'R')) ){
                q.push(make_pair(nx, ny));
                visited[nx][ny] = cnt;
            }
        }
    }
}

// in main()
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            visited[i][j] = 0;
        }
    }
    cnt = 1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if( visited[i][j] == 0 ){
                q.push(make_pair(i, j));
                visited[i][j] = cnt;
                bfs();
                cnt++;
            }
        }
    }
    cout << cnt-1 << ' ';

    cnt = 1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            visited[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if( visited[i][j] == 0 ){
                q.push(make_pair(i, j));
                visited[i][j] = cnt;
                bfs2();
                cnt++;
            }
        }
    }
    cout << cnt-1 << '\n';

적록색약이 아닌 사람과 적록색약인 사람 각 bfs 조건만 살짝 추가해서 돌려 줘도 충분히 잘 돌아간다.
</br>

11399: ATM

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

    sort(p, p+n);

    dp[0] = p[0];
    int sum = dp[0];
    for(int i = 1; i < n; i++){
        dp[i] = p[i] + dp[i-1];
        sum += dp[i];
    }

    cout << sum << endl;

운영체제 시간에 스케줄링이 생각나네
metric에 Turnaround Time이 있었는데 그 녀석을 기준으로 하는 문제다
해당 문제는 단순하게 SJF(Shortest Job First)다. 그냥 정렬하고 다 더해 주면 된다.

</br>

---

이번 방학 안에 50등 안에 들어야지
</br>