반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법


3차원 dp 점화식을 세우면 정답을 바로 구할 수 있는 문제이다.


이 문제를 풀며 느낀 것은 여러 대회에서 c++의 input, output의 속도를 위해 fastio를 알려준다.


하지만 이 문제에서 절실히 드러난 것은 fastio를 써도 결국 scanf / printf를 cin / cout이 이길 수 없다는 것이다.


같은 코드인데 scanf / printf만 AC를 받는다.(보통 fastio를 쓰면 scanf / printf나 cin / cout이나 속도가 같아진다고 말을 한다.)




다시 3차원 dp에 대해 이야기를 해보면


dp[i][j][k] :: i행 j열의 k(1~10)번째수가 몇개가 누적되어 왔는지를 의미한다.


그렇다면 dp[i][j][k]의 점화식은 다음과 같아진다.


dp[i][j][k] += dp[i][j - 1][k];

dp[i][j][k] += dp[i - 1][j][k];

dp[i][j][k] -= dp[i - 1][j - 1][k];


i, j - 1번째까지 누적되어왔던 k를 더해주고

i - 1, j번째까지 누적되어왔던 k를 더해주고

위의 두 방식에 의해 i - 1, j - 1까지 누적되어온 수가 두번 더해졌으니 그 값을 빼주면 된다.


그 후 우리는 쿼리를 통해 문제를 해결할 수 있다.



소스 코드 : 


< scanf / printf 를 이용한 AC 코드 > 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int dp[303][303][13];
int arr[303][303];
 
int main()
{
    int n;
    scanf("%d"&n);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d",&arr[i][j]);
 
    for(int i = ; i <= n ; i++)
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= 10; k++)
            {
                dp[i][j][k] += dp[i][j - 1][k];
                dp[i][j][k] += dp[i - 1][j][k];
                dp[i][j][k] -= dp[i - 1][j - 1][k];
            }
 
            dp[i][j][arr[i][j]]++;
        }
 
    int q;
    scanf("%d"&q);
 
    while (q--)
    {
        int x1, y1, x2, y2, cnt = 0;
        scanf("%d %d %d %d"&x1, &y1, &x2, &y2);
 
        int tmp[11];
        for (int i = 1; i <= 10; i++)
            tmp[i] = dp[x2][y2][i];
 
        for (int i = 1; i <= 10; i++)
        {
            tmp[i] -= dp[x1 - 1][y2][i];
            tmp[i] -= dp[x2][y1 - 1][i];
            tmp[i] += dp[x1 - 1][y1 - 1][i];
        }
 
        for (int i = 1; i <= 10; i++)
            if(tmp[i] > 0)
                cnt++;
 
        printf("%d\n", cnt);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




< fastio를 이용한 cin / cout WA 코드 > 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
 
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
 
using namespace std;
 
int dp[303][303][13];
int arr[303][303];
 
int main()
{
    fastio();
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> arr[i][j];
 
    for(int i = ; i <= n ; i++)
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= 10; k++)
            {
                dp[i][j][k] += dp[i][j - 1][k];
                dp[i][j][k] += dp[i - 1][j][k];
                dp[i][j][k] -= dp[i - 1][j - 1][k];
            }
 
            dp[i][j][arr[i][j]]++;
        }
 
    int q;
    cin >> q;
 
    while (q--)
    {
        int x1, y1, x2, y2, cnt = 0;
        cin >> x1 >> y1 >> x2 >> y2;
 
        int tmp[11];
        for (int i = 1; i <= 10; i++)
            tmp[i] = dp[x2][y2][i];
 
        for (int i = 1; i <= 10; i++)
        {
            tmp[i] -= dp[x1 - 1][y2][i];
            tmp[i] -= dp[x2][y1 - 1][i];
            tmp[i] += dp[x1 - 1][y1 - 1][i];
        }
 
        for (int i = 1; i <= 10; i++)
            if(tmp[i] > 0)
                cnt++;
 
        cout << cnt << endl;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1254번] 팰린드롬 만들기  (0) 2017.11.22
[1254번] 팰린드롬 만들기  (0) 2017.11.19
[11066번] 파일 합치기  (0) 2017.11.16
[11495번] 격자 0 만들기  (2) 2017.11.15
[1658번] 돼지 잡기  (2) 2017.11.14