백준: Silver2① - 1012, 1024, 1058

</br> 실버 2 문제들이다~~ 좋아
</br>

1012: 유기농 배추

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

연결된 배추들 집단 개수 구하기

void func(int x, int y){
    for(int i = 0; i < 4; i++){
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        if( mmap[nextX][nextY] == 1 && check[nextX][nextY] == 0 ){
            check[nextX][nextY] = 1;
            func(nextX, nextY);
        }
    }
}

// in main()
    for(int i = 0; i < t; i++){
        int cnt = 0;
        int m, n, k;
        cin >> m >> n >> k;

        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                mmap[j][k] = 0;
                check[j][k] = 0;
            }
        }

        for(int j = 0; j < k; j++){
            int x, y;
            cin >> x >> y;
            mmap[y][x] = 1;
        }

        for(int j = 0; j < n; j++){
            for(int k = 0; k < m; k++){
                if( mmap[j][k] == 1 && check[j][k] == 0 ){
                    cnt++;
                    check[j][k] = 1;
                    func(j, k);
                }
            }
        }
        cout << cnt << endl;
    }

얼마 전에 백야극광 알고리즘에서 한 거랑 거의 똑같은 게 나왔다
dfs로 간단히 가능… 경로를 다 찾아볼 필요 없으므로 체크를 하고 지우지 않는다.

</br>

1024: 수열의 합

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

연속되는 음이 아닌 정수들의 합이 n인 수열 구하기

    int a = 1;
    for(int i = 2; i < l+1; i++){
        a += i;
    }
    for(int i = l; i < 101; i++){
        if( n < a ) break;
        if( (n-a) % i == 0 ){
            for(int j = (n-a)/i + 1; j < i + (n-a)/i + 1; j++){
                cout << j << ' ';
            }
            cout << endl;
            return 0;
        }
        a += i+1;
    }

    // ************

    cout << -1 << endl;

일단 수학적으로 봤는데…

1개 합: 1 2 3 4 5 6 7 8 9 10 ...
2개 합:   3 5 7 9 11 ...
3개 합:     6 9 12 ...
4개 합:       10 ...

과 같이 규칙이 있다는 걸 알고,
그럼 a를 앞의 1, 3(1+2), 6(1+2+3), 10(1+2+3+4)… 라 하면
n - a가 l로 나누어 떨어지면 l개의 수열의 합으로 나타나질 수 있음을 알 수 있었다.

그래서 l 이상 100 이하 길이의 수열을 찾기 위해 for문을 돌린다.
만약 n이 a보다 작다면 만들 수 없으므로 break하여 탈출한다.
만약 n - a가 i로 나누어 떨어지면 i개의 합으로 가능하다. 그 인덱스도 n-a를 i로 나눈 몫으로 바로 접근할 수 있다. ex: 18) (18-6)%3 == 0, (18-6)/3 = 4. 따라서 3 + 4 = 7까지의 세 수의 합: 5, 6, 7
</br>

근데 제출했는데 틀렸다!

그 반례가 입력 1 2에 대한 출력 0 1인데, 현재 코드로는 그냥 -1을 출력한다. 다시 보니까 음이 아닌 정수라서 0도 포함해야 했다. 그래서

    a = 0;
    for(int i = 1; i < l; i++){
        a += i;
    }
    if( a == n ){
        for(int i = 0; i < l; i++){
            cout << i << ' ';
        }
        cout << endl;
        return 0;
    }

1부터 l-1까지 더해서 n이 나온다면 0을 포함한 수열이 답이 되므로 이를 확인해 주는 코드를 처음 코드의 주석으로 표시한 부분에 추가했다.

그러나 이도 저도 아니면 답이 아예 없으므로 -1을 출력한다.
</br>

1058: 친구

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

건너 친구 수가 가장 많을 때 그 수 구하기

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if( mmap[i][k] == 1 && mmap[k][j] == 1 ){
                    mmap2[i][j] = 1;
                    mmap2[j][i] = 1;
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        int cnt = 0;
        for(int j = 0; j < n; j++){
            if( mmap2[i][j] == 1 ){
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }

    if( ans == 0 ) cout << 0 << endl;
    else cout << ans-1 << endl;

문제가 말을 일부러 복잡하게 하는 건지…
대충 A - B가 친구가 B - C가 친구면 A - C도 친구로 치고 제일 친구 많은 애의 친구 수 구하기다

건너 건너라니 당연히 플로이드 워셜이다.
mmap과 mmap2에 1단 친구들을 저장해 놓고, mmap에 2단 친구들도 저장해주고 카운트해서 출력하면 된다.
자기 자신은 빼야 하니 -1이고, 만약 ans가 업데이트 되지 않았다면 0명이므로 0을 출력한다.
</br>

---

실버 2 부터는 빨리는 안 오른다.
내일 실버 1 찍어야지~~
</br>