백준: Gold4 - 1261, 1339

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

1261: 알고스팟

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

(1,1)에서 (n,m)까지 벽을 몇 번 부숴야 하는지

    queue<P> q;
    q.push(mp(0, 0));
    dp[0][0] = 0;
    int d = 0, ans = 0;
    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 || m <= ny ) continue;
            if( dp[nx][ny] > dp[x][y] + mmap[nx][ny] ){
                dp[nx][ny] = dp[x][y] + mmap[nx][ny];
                q.push(mp(nx, ny));
            }
        }
    }

    cout << dp[n-1][m-1] << endl;

처음엔 dp로 풀면 되나? 했는데, 그냥 순차적으로 증가한다고 되는 게 아니더라.
그래서 bfs로 접근하면서, `dp[x][y] = min(dp[x][y], 이전 dp값 + 0 또는 1)로 업데이트 해 주었다.
현재 지도에서 0일 경우 부술 필요 없으므로 0을 더하고, 1일 경우 벽이므로 1을 더한다. 그 값이 현재 dp의 값보다 작다면 더 좋은 경로이므로 업데이트한다.
</br>

1339: 단어 수학

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

각 알파벳을 임의의 숫자로 치환했을 때 단어들의 합이 최대가 되기를 구하기

처음에는 그리디로, 자리수가 큰 순으로 정렬 후 알파벳마다 숫자를 배정했는데, 그렇게 풀면 반례가 있더라.

ex)
10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

내가 생각한 알고리즘 대로면 A=9, B=8이 되어야 하지만, BB는 10번 나오고 A00은 한 번 나오므로 B=9, A=8을 해야 합이 더 크게 나온다.

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); j++){
            nums[s[j] - 'A'] += pow(10, s.size()-j-1);
        }
    }
    sort(nums, nums + 26, greater<>());
    int num = 9;
    int ans = 0;
    for(int i = 0; i < 26; i++){
        ans += nums[i] * num;
        num--;
    }
    cout << ans << endl;

따라서 다시 생각한 게, 일단 알파벳을 다 1이라 생각하고 그 합들을 알파벳마다 저장한다.

ex) ABC, DDDD, AD
-> A: 100 + 10 = 110
   B: 10
   c: 1
   D: 1111 + 1 = 1112

따라서 이 합대로 정렬해서, 차례대로 큰 숫자를 주면 큰 숫자와 합이 큰 게 곱해지므로 해결 된다.
</br>

---

https://ideone.com/ 직접 인풋 넣고 돌려볼 수 있는 사이트가 있더라 좋다
로컬에서는 시간 측정이 정확하지 않을 수 있어서
</br>