백준: Silver3① - 1003, 1004, 1051, 1057

</br> 실버 3 문제들~

단순 구현에서 이제 나름 dp나 이분탐색도 나온다.
</br>

1003: 피보나치 함수

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

재귀식 피보나치 함수에서 0과 1을 얼마나 호출하는 지 계산하기

int dp[41][2];


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

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

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;

        cout << dp[a][0] << ' ' << dp[a][1] << endl;

    }

간단하게 dp로 구할 수 있다. 앞부분 조금만 적어 보면 이차원으로 가능.

그런데 다른 사람 코드를 보니 0의 출력 횟수와 1의 출력 횟수의 인덱스 차이가 1씩 나고 완전히 같아서 일차원으로 만든 것도 있더라.
</br>

1004: 어린 왕자

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

제일 적게 원을 통과해서 도착하기

    for(int i = 0; i < t; i++){
        int x1,y1, x2,y2, n, cnt = 0;
        cin >> x1>>y1 >> x2>>y2 >> n;

        for(int j = 0; j < n; j++){
            int x, y, r;
            cin >> x >> y >> r;

            if( dist(x,y, x1,y1) < r && dist(x,y, x2,y2) > r ){
                cnt++;
            }
            else if( dist(x,y, x1,y1) > r && dist(x,y, x2,y2) < r ){
                cnt++;
            }
        }

        cout << cnt << endl;
    }

경로를 다 계산해야 하는 게 아니므로, 그냥 출발지와 도착지가 서로 원 안팎에 있는 지만 확인해 주면 된다.
</br>

1051: 숫자 정사각형

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

이차원 배열을 입력 받고 가장 큰 정사각형 만들기

    int ans = 0;
    for(int i = 0; i+ans < n; i++){
        for(int j = 0; j+ans < m; j++){
            for(int k = 1; i+k < n && j+k < m; k++){
                if( mmap[i][j] == mmap[i+k][j]
                    && mmap[i][j] == mmap[i][j+k]
                    && mmap[i][j] == mmap[i+k][j+k] ){
                    ans = max(ans, k+1);
                }
            }
        }
    }
    if( ans == 0 ) cout << 1 << endl;
    else cout << ans*ans << endl;

하나씩 검사해 주면 된다. 각 모서리가 모두 같은 지를 확인하고 ans를 업데이트한다.

만약 ans가 업데이트 되지 않았다면 최소 정사각형은 1이다.
생각해보니까 그냥 ans를 처음에 1로 초기화하면 되네
멍청하면 코드가 늘어난다
</br>

1057: 토너먼트

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

나도 친구도 무조건 이긴다면 친구랑 몇 강에서 붙게 될까?

    int cnt = 0;
    while( kim != im ){
        kim = (kim+1) / 2;
        im = (im+1) / 2;
        cnt++;
    }
    cout << cnt << endl;

선수들의 번호는 (1, 2) -> 1, (3, 4) -> 2, … 식이므로 (번호+1)/2와 같다.
그냥 그대로 세 주면 됨
</br>

---

딱히 이전 난이도랑 구분은 안 되는 문제들이다.
쉬우니 좋다
</br>