<링크>

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


<풀이>

시키는 대로 하면된다.

1.큰그림


재귀로 풀었는데
판때기 상태를 나타내는 2차원 배열을 인자로 받아서

4가지방향(상하좌우)로 이동시킨 모습으로 수정하고
그대로 재귀호출로 넘겨주는 방식이다.


'상' 방향으로 배열을 수정할 때 인자로 받은 배열은 call by reference이기 때문에 그대로 수정하면 맨위에있는 배열이 바뀌게 되고, 다른 방향들을 볼 때 전혀 다른 결과가 되기 때문에

함수가 호출될 때마다 인자로 넘어온 배열을 복사해서 진행했다. 
그럼 각 함수 호출마다 20*20 int배열이 필요하게 된다. 재귀호출된 depth가 깊어질 수록 메모리 사용이 커지는데   배열로만 스택에 4^depth * 400 * sizeof(int)  byte만큼의 메모리를 쓰게 된다. 
문제에 최대 5회라고 되어있으니깐 충분할 것 같아서 진행했다.

2. 각 방향으로 이동할 때

2중 for문을 돌면서 모두 체크한다.
0이 아닌 숫자가 뜨면, 내가 가는 방향으로 바로 다음 칸이 0일 때까지 쭉 간다.
그 후 다음 칸의 숫자랑 나랑 같으면 더해서 다음 칸의 숫자를 만들고 나는 0으로 없애버린다.
이 때, 한 번의 이동에서 두 번이상 더해질 수 없으므로 해당 칸의 숫자가 변했는지 체크하기 위한 배열을 또 만들었다. 이 때문에 메모리 사용이 2배로 더 늘어났을 것이다.

3. 코드를 줄이기 위한 나의 최선


똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐지기 때문에 각 방향마다 
2중 for문으로 탐색하는 순서가 달라야 한다.
상, 좌 방향은 판의 왼쪽위부터 우리가 평소하는 2중for문 순서대로 훑으면 되고
우, 하 방향은 판의 오른쪽 아래부터 반대로 훑어야한다.
toI,toJ[4]배열을 만들었다.


<소스코드>

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<stdio.h>
int pan[20][20];
int N;
int toI[4] = { -1,1,0,0 }; //상하좌우
int toJ[4] = { 0,0,-1,1 };
int ans;
void dfs(int(*)[20], int);
void progress1(int(*)[20], int, int);
void progress2(int(*)[20], int, int);
void arrCpy(int(*)[20], int(*)[20]);
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; ++i) //상,좌
        for (int j = 0; j < N; ++j) {
            scanf("%d", &pan[i][j]);
            if (pan[i][j] > ans)
                ans = pan[i][j];
        }
    dfs(pan, 0);
    printf("%d", ans);
}
void dfs(int(*p)[20], int depth)
{
    if (depth == 5)
        return;
    for (int k = 0; k < 4; ++k)
    {
        int tmpArr[20][20] = { 0, };
        arrCpy(tmpArr, p);
        if (k % 2 == 0)
            progress1(tmpArr, toI[k], toJ[k]);
        else
            progress2(tmpArr, toI[k], toJ[k]);
        dfs(tmpArr, depth + 1);
    }
    return;
}
void progress1(int(*a)[20], int toi, int toj) //상,좌
{
    int check[20][20] = { 0, }; //한번 합쳐진 좌표인지 확인용
    for (int i = 0; i < N; ++i) //상,좌
        for (int j = 0; j < N; ++j)
            if (a[i][j] != 0)
            {
                int curi = i;
                int curj = j;
                int tmp = a[curi][curj];
                while (curi + toi >= 0 && curj + toj >= 0 && a[curi + toi][curj + toj] == 0)
                {
                    a[curi][curj] = 0;
                    curi += toi;
                    curj += toj;
                }
                a[curi][curj] = tmp;
                if (curi + toi >= 0 && curj + toj >= 0
                    && a[curi + toi][curj + toj] == a[curi][curj]
                    &&!check[curi+toi][curj+toj])
                {
                    int sum = a[curi + toi][curj + toj] + a[curi][curj];
                    if (sum > ans)
                        ans = sum;
                    a[curi + toi][curj + toj] = sum;
                    check[curi + toi][curj + toj] = 1;
                    a[curi][curj] = 0;
                }
 
            }
 
 
}
void progress2(int(*a)[20], int toi, int toj) //우,하
{
    int check[20][20] = { 0, }; //한번 합쳐진 좌표인지 확인용
    for (int i = N - 1; i >= 0; --i) //우,하
        for (int j = N - 1; j >= 0; --j)
            if (a[i][j] != 0)
            {
                int curi = i;
                int curj = j;
                int tmp = a[curi][curj];
                
                while (curi + toi <N && curj + toj < N && a[curi + toi][curj + toj] == 0)
                {
                    a[curi][curj] = 0;
                    curi += toi;
                    curj += toj;
                }
                a[curi][curj] = tmp;
                if (curi + toi <N && curj + toj<N
                    && a[curi + toi][curj + toj] == a[curi][curj]
                    && !check[curi + toi][curj + toj])
                {
                    int sum = a[curi + toi][curj + toj] + a[curi][curj];
                    if (sum > ans)
                        ans = sum;
                    a[curi + toi][curj + toj] = sum;
                    check[curi + toi][curj + toj] = 1;
                    a[curi][curj] = 0;
                }
 
            }
}
void arrCpy(int(*a)[20], int(*b)[20])
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            a[i][j] = b[i][j];
}
cs


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 15685 드래곤커브  (0) 2018.09.30
백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

D앞의 수를 A,B,C라 하면
A+B+C=D 를 만족하면 D는 좋은 수이다.
같은 수를 여러번 더해도 된다. 수열의 수로 만들 수 있는 모든 조합을 세어보려면 
1 2 3 5 7 10
1 + 1 + 1
1 + 1 + 2
1 + 1 + 3
,,,
10 + 10 + 10

일케 해야되는데 N^3이 걸린다. N이 5000이라 시간초과가 뜰 것이다.

A+B=D-C를 이용하면 된다.
D를 하나 찝어서 D의 앞의 수(C)를 다 빼본다.
그 후 A+B가 지금까지 나온적이 있었냐만 보면 된다.
A와 B는 AA가 돼도 되고 AB, BB가 되어도 되며 C가 섞여도 된다. 왜냐면 같은 수를 여러번 더해도 되기 때문이다. 그 말은 D의 앞에 있는 두 수로 만든 조합이면 뭐든 상관없다는 뜻이다.

예를들면)
1 2 3 4 5 6 7
D=6, C=1 // 6-1 = 5 -> 5를 6 앞의 어떤 두 수로 만들어도 상관없다. 1이 섞여도 된다.

5라는 조합이 나왔었는지 확인한 뒤, 있으면 정답을 늘려주고 바로 break를 해서 나와줘야 한다. 중복해서 셀 수 있기 때문이다.

6-1,6-2,6-3,6-4,6-5가 끝난 뒤에는
(D=7)도 똑같은 방식으로 확인해야하는데
그럼 현재의 (D=6)는 새로 올 (D=7)의 앞의 수가 되기 때문에
현재의 (D=6)으로 만들 수 있는 조합을 추가해줘야한다.

현재의 D=6일때
11,12,13,14,15
22,23,24,25
33,34,35
44,45
55 의 조합이 이미 체크되어있었으므로 확인 할 수 있었던 것이다.

6이 새로 추가됐을때
16,26,36,46,56,66 을 추가해줘야 다음번부터 체크할 수 있다.
따라서 맨앞부터 현재의D까지 생기는 조합을 새로 추가해준다.

처음에는 set으로 구현했다가 시간초과가 떴다. 
set에서 있냐 없냐는 판단할 때 logN이 걸리는데 그럼 결국 N^2 * logN = 2억이 넘기 때문에 시간 초과가 뜬 것 같다.
메모리를 좀 빌려와서 배열에 체크하는 방식으로 바꾸니깐 통과되었다.
[D-C] 가 1이면 지금까지 나왔던 조합이라 생각한다.
이 때 D-C의 범위는 곧 A+B의 범위이고
-200000~200000이다.
그대로 오른쪽으로 20만 옮겨서 구현했다.


<소스코드>

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
#include<set>
#include<stdio.h>
using namespace std;
int a[5000];
int is[500000];
set<int> s;
int main()
{
    int N;
    int ans = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", a + i);
    
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int D_C = a[i] - a[j];
            if (is[D_C+200000])
            {
                ++ans;
                break;
            }
        }
        for (int j = 0; j <= i; ++j)
            is[a[i] + a[j] + 200000] = 1;
    }
    printf("%d", ans);
}
cs


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 9011 순서 :: 들짐승  (1) 2018.07.22
백준 8982 수족관1 :: 들짐승  (0) 2018.07.22

<링크>

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



<소스코드>

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
#include<stdio.h>
int num[11];
int opCnt[4];
int N;
int min=1100000000, max=-1100000000;
void recur(int, int);
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", num + i);
    for (int i = 0; i < 4; ++i)
        scanf("%d", opCnt + i);
    recur(num[0], 1);
    printf("%d\n%d", max, min);
}
void recur(int res,int k)
{
    if (k == N)
    {
        if (res > max)
            max = res;
        if (res < min)
            min = res;
    }
    for (int i = 0; i < 4; ++i)
    {
        if (opCnt[i])
        {
            --opCnt[i];
            switch (i)
            {
            case 0:recur(res + num[k], k + 1); break;
            case 1:recur(res - num[k], k + 1); break;
            case 2:recur(res*num[k], k + 1); break;
            case 3:recur(res / num[k], k + 1); break;
            }
            ++opCnt[i];
        }
    }
}
cs


<풀이>

opCnt배열에 각 연산자 기호의 개수를 입력받는다.

예를 들어 
+ - * /
2 1 0 1

이라면,

++-/
++/-
+-+/
+-/+
+/+-
+/-+
...
/+-+
/-++

처럼
모든 가능한 연산자 순서를 다 적용시켜서 나오는 결과값을 보면 된다.


순열과 비슷하지만 한 연산자가 여러 개 있을 수 있기 때문에
각각의 연산자 cnt를 감소시키며 dfs를 하고, cnt가 0이 되면 해당 연산자는 다 본 것이기 때문에 넘어간다.
호출되기 직전에 cnt를 감소시켜주고, 호출이 끝나면 다시 cnt를 증가시켜줘야한다. 
이는 순열만들기의 dfs에서 visit를 체크하는 방법과 유사하다. 
자신이 사용했다가 끝나면 다시 원상복귀를 시켜줘야 나중에 사용할 때 문제가 없다.



저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 15686 치킨배달  (0) 2018.09.30
백준 1107 리모컨  (2) 2018.07.26
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바