백준: Gold5⑥ - 1915, 1916, 2023

</br> 계속 계속
</br>

1915: 가장 큰 정사각형

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

가능한 가장 큰 정사각형 구하기

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

알고리즘 강의 때 비슷한 문제를 푼 적이 있다
dp[i] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1인데,

11
1  > 2

111
12  > 2

1110
1221
123  > 2

대충 이런 느낌으로 dp를 만들어서 최대 변의 길이를 구할 수 있다.
</br>

1916: 최소비용 구하기

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

방향 그래프에서 최단 경로 구하기

    for(int i = 1; i <= n; i++){
        dist[i] = INT_MAX;
    }
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[departure] = 0;
    pq.push(mp(0, departure));
    while( pq.size() ){
        int a = pq.top().second;
        int w = pq.top().first;
        pq.pop();
        if( w > dist[a] ) continue;
        for(int i = 0; i < graph[a].size(); i++){
            int na = graph[a][i].second;
            int nw = graph[a][i].first + w;
            if( nw < dist[na] ){
                dist[na] = nw;
                pq.push(mp(dist[na], na));
            }
        }
    }
    cout << dist[arrival] << endl;

바로 전 포스트(https://cyj893.github.io/algorithm/Algorithm11_5/)의 1753번과 똑같은 다익스트라 문제다

</br>

2023: 신기한 소수

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

수 abcdef에서 abcdef, abcd, abc, ab, a 전부 소수인 수 구하기

bool isPrime(int k){
    for(int i = 2; i*i <= k; i++){
        if( k % i == 0 ) return false;
    }
    return true;
}
void func(int k, int d){
    if( d == n ){
        cout << k << endl;
        return;
    }
    for(int i = 1; i < 10; i += 2){
        int nk = k*10 + i;
        if( isPrime(nk) ){
            func(nk, d+1);
        }
    }
}

// in main()
    func(2, 1);
    func(3, 1);
    func(5, 1);
    func(7, 1);

소수니까 에라토스테네스의 체를 써야지 했는데 메모리 제한이 4메가 밖에 안 됐다.
그래서 생각해 보니, 가장 첫자리 수도 소수가 되어야 하므로 반드시 2, 3, 5, 7로 시작해야 한다.
그 뒤도 다 그렇게 되는데 짝수는 빼고 홀수만 더해주며 체크해주면 되니까 경우의 수가 그렇게 많지는 않다.
</br>

---

다음엔 골드 4를 풀어 볼까
</br>