백준: Class 4 - 11725, 16953, 11660

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

11725: 트리의 부모 찾기

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

void func(int k){
    for(int i = 0; i < tree[k].size(); i++){
        if( parent[tree[k][i]] ) continue;
        parent[tree[k][i]] = k;
        func(tree[k][i]);
    }
}

// in main()
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    parent[1] = 1;
    func(1);

    for(int i = 2; i <= n; i++){
        cout << parent[i] << '\n';
    }

간단한 트리 탐색
1 기준으로 탐색 시작하고 부모를 표시하면 끝
</br>

16953: A -> B

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

방법 1.

    priority_queue< pair<long long, int>, vector<pair<long long, int>>, greater<> > pq;
    pq.push(make_pair(0, a));
    visited[a] = 1;
    int ans = -1;
    while( pq.size() ){
        long long now = pq.top().second;
        int d   = pq.top().first;
        pq.pop();
        if( now == b ){
            ans = d+1;
            break;
        }
        long long now2 = now*2;
        long long now1 = now*10 + 1;
        if( now2 <= b && visited.count(now2) == 0 ){
            pq.push(make_pair(d+1, now2));
            visited[now2] = 1;
        }
        if( now1 <= b && visited.count(now1) == 0 ){
            pq.push(make_pair(d+1, now1));
            visited[now1] = 1;
        }
    }
    cout << ans << endl;

이번에도 우선순위 큐를 이용한 bfs로 찾아 보았다

</br>

근데 풀다 보니 이거 가는 방법도 2개 뿐이고… b는 어차피 끝자리 수가 짝수거나 1일 수 밖에 없네

방법 2.

    int cnt = 1;
    while( 1 ){
        if( b == a ) break;
        if( b < a ){
            cout << -1 << endl;
            return 0;
        }
        if( b % 2 == 0 ) b /= 2;
        else if( b % 10 == 1 ) b /= 10;
        else{
            cout << -1 << endl;
            return 0;
        }
        cnt++;
    }
    cout << cnt << endl;

그래서 b에서 a로 가는 걸 해 봤다
훨씬 쉽고 좋다
</br>

11660: 구간 합 구하기 5

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

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> mmap[i][j];
        }
        dp[i][1] = mmap[i][1];
        for(int j = 2; j <= n; j++){
            dp[i][j] = dp[i][j-1] + mmap[i][j];
        }
    }

    while( m-- ){
        int x1,y1, x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;

        int ans = 0;

        for(int i = x1; i <= x2; i++){
            if( y1 == 0 ) ans += dp[i][y2];
            else ans += dp[i][y2] - dp[i][y1-1];
        }

        cout << ans << '\n';
    }

이것도 구간 합이라서, dp를 만든다
dp[i][j] = dp[i]행의 j번째 까지의 합

ex) 백준 예제 1
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

dp
1 3 6 10
2 5 9 14
3 7 12 18
4 9 15 22

그럼 좌표 두 개를 받으면 해당하는 행들의 구간 합을 다 더해주면 된다
</br>

---

자꾸 포스트에 쓰려고 예제 출력한 부분을 안 지워서 한 번씩 틀리네ㅜㅜ
정신이 없다
</br>