반응형

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

 

10844번: 쉬운 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을 세우면 될지 생각해보면 쉽게 답이 나오는 경우가 많았습니다.

 

이번에도 먼저 10X100 배열을 만들어서 값들을 넣어 보았고 바로 점화식이 떠올라 쉽게 답을 구할 수 있었습니다.

 

일단 첫째자리에 올 수 있는 숫자는 0을 제외한 1~9까지의 수이므로 9개입니다. 이를 표로 표현하면 다음과 같습니다.

 

 

그 후 두번째 자리에 올 수 있는 수들은 첫 번째 자리에 오는 수와 값이 1이 차이가 나면 되므로 앞의 수가 지금의 수와 절댓값이 1 차이가 나면 됩니다. 따라서 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + dp[ i - 1 ][ j + 1 ]이 됩니다. 하지만 0과 9는 각각 1과 8만 올 수 있으므로 예외 처리해주면 됩니다.

 

 

마지막으로 N번째 열의 값들을 모두 더해주면 N의 자리수의 계단수들을 모두 구할 수 있습니다.

 

하지만 구하고자하는 값이 int형 범위를 넘어서는 값들이고 문제의 조건에서 1,000,000,000으로 나눈 나머지 값을 출력하라고 했으므로 모든 연산이 끝나고 1,000,000,000으로 나눈 나머지 값으로 값을 경신해줍니다.

 

[ 소스 코드 ]

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
#include <iostream>
 
using namespace std;
 
int N;
long long dp[10][101];                    //각 숫자가 들어갈 수 있는 개수를 저장할 배열
 
int main()
{
    cin >> N;
 
    long long cnt = 0;                    //총 개수를 저장할 변수
 
    for (int i = 1; i < 10; i++) {        //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로
        dp[i][1] = 1;                    //모두 1로 경신
    }
 
    for (int i = 2; i <= N; i++) {        //2자릿수 부터 돌면서
        for (int j = 0; j < 10; j++) {
            if (j == 0) {                //0일 때는 1밖에 올 수 없으므로
                dp[j][i] = dp[1][i - 1];
            }
            else if (j == 9) {            //9일 때는 8밖에 올 수 없으므로
                dp[j][i] = dp[8][i - 1];
            }
            else {                        //값이 1차이나는 수들의 값을 모두 더해줌
                dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
            }
            dp[j][i] %= 1000000000;        //더해준 값을 1000000000으로 나눈 나머지로 경신
        }
    }
 
    for (int i = 0; i < 10; i++) {
        cnt += dp[i][N];                //각 숫자마다 올 수 있는 숫자들을 더하고
        cnt %= 1000000000;                //1000000000으로 나눈 나머지로 경신해준다.
    }
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30
[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
반응형

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

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 nCm의 값은 n-1Cm-1 + n-1Cm으로 표현할 수 있으므로 앞에서 구한 값을 더해서 자신의 값을 계산할 수 있습니다. 따라서 위와 같은 점화식을 사용해서 dp배열을 만들어 적용시켜 주었습니다. 

 

하지만 계산해야 할 수가 정수형으로 표현할 수 있는 값을 벗어나기에 숫자들을 string의 형태로 입력받고 string을 더해주는 함수를 따로 만든 후 각 숫자들을 더해주었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <string>
 
using namespace std;
 
string dp[101][101];
 
string sum(string a, string b)                //a와 b를 더해주는 함수
{
    string ans = "";
 
    int lenA = a.size();
    int lenB = b.size();
    int len = max(lenA, lenB);
    int sum = 0;
    char num;
 
    while (lenB != len) {
        b = '0' + b;
        lenB++;
    }
    while (lenA != len) {
        a = '0' + a;
        lenA++;
    }
 
    for(int i=len - 1;i>=0;i--){
        sum = a[i] + b[i] - '0' - '0' + sum;
        num = sum % 10 + '0';
        ans = num + ans;
        sum /= 10;
    }
    if (sum != 0) {
        ans = (char)(sum + '0') + ans;
    }
 
 
    return ans;
}
 
string change(int num)                        //특정 int를 string의 형태로 바꿔주는 함수
{
    string ans = "";
    if (num > 99) {
        ans = "100";
    }
    else if(num > 9) {
        ans += (char)(num / 10 + '0');
        ans += (char)(num % 10 + '0');
    }
    else {
        ans = (char)(num + '0');
    }
 
    return ans;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= 100; i++) {
        dp[i][1] = change(i);
    }
    
 
    for (int i = 2; i <= 100; i++) {
        for (int j = 2; j <= i; j++) {
            if (i == j) {                    //n과 m이 같을 때는 1이므로
                dp[i][j] = "1";
            }
            else {                            //아닐 때는 nCm = n-1Cm-1 + n-1Cm을 대입
                dp[i][j] = sum(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
 
    cout << dp[n][m];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
반응형

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

 

1509번: 팰린드롬 분할

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 dp라는 이차원 배열을 만들어서 팰린드롬인지 체크를 해야 합니다. dp [1][3]이 1이라면 문자열의 1번부터 3번까지는 팰린드롬이라는 뜻입니다.

 

그리고 어디부터 어디까지 팰린드롬인지 체크하기 위해서는 문자열의 끝에서부터 시작해야합니다.

 

먼저 글자가 하나일 때는 모든 글자가 팰린드롬이므로 dp [i][i]는 1로 채워줍니다.

 

그러고 나서 4번째 행부터 체크를 시작합니다. 나의 바로 앞까지 만약 팰린드롬인 문자열이 있다면 나와 팰린드롬인 문자열의 바로 앞 문자와 비교해서 같으면 나도 팰린드롬이라는 결과를 얻을 수 있습니다.

 

즉, dp [i+1][j-1]이 1이라면 i번째 문자열과 j번째 문자열이 같다면 dp [i][j]는 1이 됩니다.

 

이렇게 모든 dp배열을 채우면 몇 번 문자부터 몇번 문자까지 팰린드롬인지 모두 체크할 수 있고, 이것을 이용해서 팰린드롬을 최소 몇 개로 나타낼 수 있는지 구할 수 있습니다.

 

이번엔 반대로 앞에서부터 시작합니다.

 

ans배열을 만들고, 기록을 시작합니다. ans배열은 i번째 문자열까지 팰린드롬을 최소로 나눌 수 있는 수를 기록할 배열입니다.

 

만약 ans [i]의 값을 구하고 싶다면 j번부터 i번까지 팰린드롬인 문자열을 찾고, 만약 팰린드롬이라면 ans [i] 값과 ans [j-1]+1의 값을 비교해 더 작은 숫자를 대입해 줍니다. 왜냐하면 ans [j-1]은 j-1번째 문자열까지의 최솟값을 저장했기 때문입니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <string>
 
using namespace std;
 
string str;
 
int dp[2501][2501];                    //팰린드롬인지 판별할 배열
int ans[2501];                        //최솟값을 저장할 배열
 
int main()
{
    cin >> str;
    str = ' ' + str;
    for (int i = str.size(); i >= 1; i--) {        //dp[start][end] start부터 end까지 팰린드롬이라면 1 아니라면 0
        for (int j = str.size(); j >= i; j--) {
            if (i == j) dp[i][j] = 1;
            else if (j - i == 1) {
                if (str[i] == str[j]) {
                    dp[i][j] = 1;
                }
            }
            else {
                if (dp[i + 1][j - 1] == 1) {
                    if (str[i] == str[j]) {
                        dp[i][j] = 1;
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= str.size()-1; i++) {
        ans[i] = 3000;
        for (int j = 1; j <= i; j++) {
            if (dp[j][i] == 1) {                //j부터 i까지 팰린드롬이라면 j-1의 값보다 1 더 크므로
                ans[i] = min(ans[i], ans[j - 1] + 1);
            }                                    //하지만 갱신이 되어있는 값이 더 작을 수도 있으므로
        }                                        //둘을 비교해서 더 작은 값을 대입
    }
 
 
    cout << ans[str.size()-1];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
반응형

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

 

1208번: 부분수열의 합 2

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

N개의 정수의 모든 부분 수열을 구하기 위해서는 O(2^N)의 시간이 걸립니다.

 

이 문제에서 N은 40개이므로 총 2^40의 시간이 필요한데 1초는 매우 부족한 시간이므로 N을 반으로 나누어 2^20 * 2 = 2^21의 시간이 걸리도록 했습니다.

 

먼저 왼쪽의 부분 수열의 합을 모두 구해 map에 넣고, 오른쪽 부분 수열의 합을 S의 값과 비교하여 cnt에 map[S-sum]을 더해주었습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int N, S;
int arr[41];
unordered_map<int, int> map;
int sum = 0;
long long cnt = 0;
 
void leftDFS(int level)                //왼쪽 반의 모든 조합을 map에 저장
{
    if (level == N / 2) {
        map[sum]++;
        return;
    }
 
    sum += arr[level];
    leftDFS(level + 1);
    sum -= arr[level];
    leftDFS(level + 1);
}
 
void rightDFS(int level)            //오른쪽 반의 모든 조합을 S와 비교해
{                                    //cnt에 더해줌
    if (level == N) {
        cnt += map[S - sum];
        return;
    }
 
    sum += arr[level];
    rightDFS(level + 1);
    sum -= arr[level];
    rightDFS(level + 1);
}
 
int main()
{
    cin >> N >> S;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    leftDFS(0);
    rightDFS(N / 2);
 
    if (S == 0) cnt--;                //S가 0인 경우 공집합이 2번 들어가므로 1을 빼준다.
 
    cout << cnt;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2407번 - 조합 (C++)  (0) 2022.05.27
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22
반응형

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

 

17387번: 선분 교차 2

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

www.acmicpc.net

 

[ 문제풀이 ]

 

선분이 교차할 때의 조건을 알아야 풀 수 있는 문제입니다.

 

 

위와 같이 2개의 선분을 서로 교차한다고 말합니다. 이때 p1과 p2를 이은 선분을 벡터 v1이라고 하면 v1 = p2 - p1이 됩니다. 이와 같은 원리로 v2 = p3 - p1, v3 = p4 - p1이라고 하면 다음과 같이 나타낼 수 있습니다.

 

 

이때 v1과 v2를 외적 하면 반시계 방향이므로 양수가 나오고, 반대로 v1과 v3를 외적 하면 시계방향이므로 음수가 나옵니다. 위 결과로 보아 벡터들의 외적 값을 구하고 그 방향이 반대라면 선분이 교차한다고 표현할 수 있습니다.

 

 

하지만 위와 같은 상황에서는 조건을 만족하지만 교차한다고 표현할 수 없습니다.

 

이 때에는 또 다른 벡터를 이용해서 구해줍니다. 즉, v4 = p4 - p3, v5 = p2 - p3, v6 = p1 = p3일 때 v4를 기준으로 모두 같은 방향에 있기 때문에 조건을 만족하지 않습니다.

 

 

따라서 ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0이 되어야 합니다.

 

다른 예외 사항도 몇 가지가 있습니다.

 

3개의 점이 한 직선상에 있거나 4개의 점이 한 직선상에 있는 경우입니다.

 

 

위와 같은 경우 p1, p2, p3가 같은 직선상에 있고, ccw(p1, p2, p3)는 0이 나오게 됩니다.

 

즉, ccw(p1, p2, p3) * ccw(p1, p2, p4) == 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0 이거나,

ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) == 0을

 

 

마지막으로 위와 같은 상황에서는 모든 ccw가 0이므로 다른 조건으로 교차 여부를 판단해야 합니다. 한 직선을 기준으로 p1 < p2와 p3 < p4를 만족한다면 p2 > p3와 p4 > p1을 만족한다면 교차한다고 표현할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
struct pos {
    long long x;
    long long y;
};
 
pos arr[4];
 
bool cmp(pos left, pos right)
{
    if(left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    long long cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    for (int i = 0; i < 4; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    sort(arr, arr + 2, cmp);
    sort(arr + 2, arr + 4, cmp);
    int l1 = closs(arr[0], arr[1], arr[2]) * closs(arr[0], arr[1],arr[3]);
    int l2 = closs(arr[2], arr[3], arr[0]) * closs(arr[2], arr[3], arr[1]);
    if (l1 == 0 &&l2 == 0) {            //두 선이 일직선상에 있을 때
        if (cmp(arr[2], arr[1]) && cmp(arr[0], arr[3])) {
            cout << 1;
            return 0;
        }
    }
    else if (l1 <= 0 && l2 <= 0) {
        cout << 1;
        return 0;
    }
 
    cout << 0;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21
반응형

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

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

 

[ 문제풀이 ]

 

처음에 풀이 방법을 떠올리기까지 30분 정도 걸린 것 같습니다.

 

먼저 상어의 속도와 관련해서 일정 속도 이상이면 제자리에 여러 번 도착한다는 것을 알았습니다. 그렇다면 제자리로 오기까지의 속도는 시뮬레이션 결과에 큰 영향을 미치지 않는다고 생각을 했고, 제자리에 오는 데 걸리는 시간으로 속도를 나누어 주었습니다. 그리고 속도를 그 나머지 값으로 경신해주었습니다.

위의 그림을 보면 총 이동거리 10일 때 제자리로 돌아온다는 것을 알 수 있습니다. 바로 총 거리 - 1을 두 배 해준 값이 됩니다. 따라서 모든 상어의 속도 s를 (총 거리 - 1) * 2로 나눈 나머지 값으로 경신시켜줍니다. 그렇게 되면 시뮬레이션 시간도 대폭 감소될 것이고 시간제한도 피할 수 있을 것입니다.

 

이후 시뮬레이션을 통해 상어들을 이동시켜 주었고, visited배열을 통해서 미리 도착해 있던 상어가 있다면 크기 비교 후 더 작다면 없애고, 더 크다면 방금 도착한 상어를 없애주는 방법으로 구현하였습니다.

 

 

[ 소스 코드 ]

 

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
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstring>
 
using namespace std;
 
struct shark {
    int r;
    int c;
    int s;
    int d;
    int z;
};
 
int R, C, M;
shark arr[10001];                    //각 상어의 정보를 저장발 배열
int dr[5] = { 0,-1,1,0,0 };            //방향 배열
int dc[5] = { 0,0,0,1,-1 };
int visited[101][101];                //상어가 도착한 장소에 상어가 있는지 체크하기 위한 배열
 
int main()
{
    cin >> R >> C >> M;
    int idx = 1;
    int sum = 0;
 
    for (int i = 1; i <= M; i++) {
        int r, c, s, d, z;
        scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
        if (d < 3) {                //일정 속도 이상이면 여러번 제자리로 돌아오기 때문에
            s %= 2 * (R - 1);        //총 (길이-1)*2로 나눈 나머지 값을 속도에 넣어준다.
        }
        else {
            s %= 2 * (C - 1);
        }
        arr[i] = { r,c,s,d,z };
    }
 
    while (idx <= C)
    {
        memset(visited, 0, sizeof(visited));
        int min = 999;
        int x = 987654321;
        for (int i = 1; i <= M; i++) {        //현재 사람과 같은 위치에 있는 상어 중
            if (arr[i].r == 0) continue;    //가장 땅에 가까운 상어의 번호를 x에 저장
            if (idx == arr[i].c) {
                if (min > arr[i].r) {
                    min = arr[i].r;
                    x = i;
                }
            }
        }
        if (x != 987654321) {                //x가 경신 되었다면 그 상어를 없애고
            sum += arr[x].z;                //sum에 크기를 더해준다.
            arr[x] = { 0 };
        }
 
        for (int i = 1; i <= M; i++) {        //모든 상어를 움직인다.
            if (arr[i].r == 0) continue;
            int rr = arr[i].r;
            int cc = arr[i].c;
            for (int j = 0; j < arr[i].s; j++) {
                rr += dr[arr[i].d];
                cc += dc[arr[i].d];
                if (arr[i].d == 1) {
                    if (rr == 1) {
                        arr[i].d = 2;
                    }
                    else if (rr < 1) {
                        arr[i].d = 2;
                        rr = 2;
                    }
                }
                else if (arr[i].d == 2) {
                    if (rr == R) {
                        arr[i].d = 1;
                    }
                    else if (rr > R) {
                        rr = R - 1;
                        arr[i].d = 1;
                    }
                }
                else if (arr[i].d == 3) {
                    if (cc == C) {
                        arr[i].d = 4;
                    }
                    else if (cc > C) {
                        cc = C - 1;
                        arr[i].d = 4;
                    }
                }
                else if (arr[i].d == 4) {
                    if (cc == 1) {
                        arr[i].d = 3;
                    }
                    else if (cc < 1) {
                        arr[i].d = 3;
                        cc = 2;
                    }
                }
            }
            if (visited[rr][cc] == 0) {        //만약 처음 상어가 도착했다면
                visited[rr][cc] = i;        //visited배열에 상어 번호를 저장
                arr[i].r = rr;
                arr[i].c = cc;
            }
            else {                            //이미 와 있던 상어가 있다면
                if (arr[i].z > arr[visited[rr][cc]].z) {
                    arr[visited[rr][cc]] = { 0 };
                    visited[rr][cc] = i;    //크기를 비교 후 더 크면
                    arr[i].r = rr;            //visited배열을 경신해준다
                    arr[i].c = cc;
                }
                else {
                    arr[i] = { 0 };            //더 작다면 더 작은 상어를 없앤다.
                }
            }
        }
        idx++;                //오른쪽으로 옮긴다.
    }
 
    cout << sum;        //결과 출력
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21
반응형

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

 

16946번: 벽 부수고 이동하기 4

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

매 벽마다 움직일 수 있는 공간을 체크하게 되면은 최악의 경우 O(N*M*N*M)이 되어서 시간 초과가 날 확률이 높기 때문에 배열을 한 번만 돌면서 문제를 해결할 방법을 찾아야 했습니다.

 

일단 값을 입력받고, 전체 배열을 돌면서 값이 '1'인 좌표에는 최종 정답 배열에 1을 더해주었고, '0'인 좌표마다 모두 들러서 빈 공간의 개수를 체크했습니다. 

 

그리고 빈 공간에 방문할 때마다 방문을 체크해주기 위해 배열 값을 'a'로 경신해 주었습니다.

 

또한 벽을 만나게 되면 벽의 좌표를 vect배열에 넣어주고 bfs함수의 마지막에 각 좌표에 카운트한 값을 더해주었습니다.

위 과정을 거치면 아래와 같은 결과를 얻을 수 있습니다.

모든 좌표에 대해 위의 과정을 거치면 다음과 같은 결과를 얻을 수 있습니다.

arr 배열
ans 배열

 

 

[ 소스 코드 ]

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
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
int N, M;
char arr[1001][1001];                            //값을 입력 받을 배열
int ans[1001][1001];                            //정답을 기록할 배열
int visited[1001][1001];                        //방문을 체크할 배열
int dy[4] = { -1,1,0,0 };                        //방향 배열
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
};
 
void bfs(int y, int x)
{
    queue<pos> q;
    vector<pos> vect;
 
    q.push({ y,x });
    arr[y][x] = 'a';
 
    int cnt = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = curY + dy[i];
            int xx = curX + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '0') {
                    arr[yy][xx] = 'a';                                //배열값을 'a'로 초기화하면서 다시 방문하지 못하게 한다.
                    cnt++;                                            //갈 수 있는 곳의 수를 저장
                    q.push({ yy,xx });
                }
                if (arr[yy][xx] == '1' && visited[yy][xx] != 1) {    //벽을 만나면 visited에 기록하고 좌표를 저장
                    visited[yy][xx] = 1;
                    vect.push_back({ yy,xx });
                }
            }
        }
    }
 
    for (int i = 0; i < vect.size(); i++) {
        int yy = vect[i].y;
        int xx = vect[i].x;
        visited[yy][xx] = 0;                        //방문 기록을 없애고
        ans[yy][xx] += cnt;                            //해당 좌표에 cnt값을 더해줌
    }
}
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == '0') {
                bfs(i, j);                            //해당 배열의 값이 '0'이라면
            }                                        //bfs를 돌린다
            else if (arr[i][j] == '1') {
                ans[i][j]++;                        //해당 값이 '1'이라면 총 카운트 수에서 1을 더해준다
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << ans[i][j] % 10;                    //10으로 나눈 나머지 값을 출력한다.
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 12100번 - 2048(Easy) (C++)  (0) 2022.05.21
반응형

 

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

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

 

문제의 조건

[ 문제풀이 ]

구현 방법은 그렇게 어렵지는 않았으나 생각보다 까다로운 문제였습니다. 

 

먼저 합쳐야 하는 숫자들을 판단해야 했습니다. 합쳐지는 숫자들은 한쪽 방향으로 움직였을 때 충돌하는 숫자와 같은 값을 가져야 했고, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다는 조건이 있었습니다.

 

이러한 조건을 만족하기 위해서 방향을 정해 움직였을 때 어떠한 결과가 나오는지 구현할 수 있는 함수를 먼저 만들었습니다.

위와 같은 상황에서 위로 블록을 이동시키면 다음과 같은 결과가 나옵니다.

4와 4는 같은 숫자이지만 합쳐지지 않았는데, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다는 조건 때문입니다.

 

그렇다면 이를 어떤 식으로 구현해야 할까요?

 

블록을 움직일 방향이 왼쪽일 때를 예로 들면 왼쪽에 있는 블록부터 합쳐지기 때문에 왼쪽부터 오른쪽으로 배열을 탐색하면서 오른쪽에 있는 블록이 나와 같은 값을 가지고 있는지 체크하고, 같다면 합치고, 같지 않다면 그대로 두는 방법으로 구현했습니다.

 

그리고 합치는 과정을 모두 거친 후 모든 블록들을 왼쪽으로 밀어야 했는데 배열을 왼쪽부터 오른쪽으로 탐색하며 0이 아닌 숫자를 만나면 제일 왼쪽 칸부터 차곡차곡 쌓아주는 방식으로 구현했습니다.

 

하지만 여기서 문제가 발생했는데, 4방향을 모두 구현하기 위해서는 함수가 매우 길어질 것이라고 생각했습니다.

 

함수가 길어지면 실수를 할 수도 있고, 디버깅을 할 때도 쉽지 않을 것이라고 생각이 들어서 배열을 90도씩 돌리면서 한쪽으로 밀면 네 방향으로 움직일 수 있을 것이라고 생각했습니다.

 

마지막으로 재귀 함수를 통해서 최댓값을 구했습니다.

 

백트래킹을 위해서 temp라는 배열을 만들고 temp배열에 arr를 저장하고 재귀함수를 빠져나올 때 arr에 다시 temp를 저장하는 방식으로 구현했습니다.

 

만약 5번을 다 움직였다면 arr배열을 모두 탐색하며 가장 큰 숫자를 ans에 넣었고, ans를 출력했습니다.

 

[ 소스 코드 ]

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
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
 
using namespace std;
 
int N;
int arr[21][21];
int ans = 0;
 
void move()                                                //블럭들을 합치고 옮기는 함수
{
    for (int i = 0; i < N; i++) {
        int before = 0;
        int y;
        int x;
        for (int j = 0; j < N; j++) {
            if (before == 0) {                            //왼쪽 블럭이 합쳐지지 않았을 때
                if (arr[i][j] != 0) {                    //빈 블럭이 아니라면
                    before = arr[i][j];                    //합쳐질 블럭과 비교하기 위해 before 변수에 값을 넣어준다.
                    y = i;                                //비교를 위해 좌표를 저장
                    x = j;
                }
            }
            else {
                if (arr[i][j] != 0) {                    //왼쪽에 블럭이 있다면
                    if (before == arr[i][j]) {            //충돌하는 블럭의 값이 같다면
                        arr[y][x] = before * 2;            //블럭의 값을 2배로 바꿔주고
                        arr[i][j] = 0;                    //충돌한 블럭을 제거
                        before = 0;                        //before을 0으로 초기화 시켜준다.
                    }
                    else {                                //만약 값이 다르다면
                        before = arr[i][j];                //before을 지금 좌표의 값으로 바꿔주고
                        y = i;                            //좌표를 저장한다.
                        x = j;
                    }
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {                        //합치는 과정이 끝나면
        int cnt = 0;
        for (int j = 0; j < N; j++) {                    //왼쪽에서부터 차례로
            if (arr[i][j] != 0) {                        //빈 블럭이 아니라면
                if (cnt != j) {                            //왼쪽에 빈 공간이 있다면
                    arr[i][cnt] = arr[i][j];            //왼쪽으로 옮기고
                    arr[i][j] = 0;                        //지금 칸을 비워준다.
                }
            cnt++;                                        //비어 있는 칸을 오른쪽으로 한칸씩 옮겨준다.
            }
        }
    }
}
 
void turn(int num)                                        //num만큼 90도 회전
{
    int temp[21][21];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int k = 0; k < num; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = temp[j][N - i - 1];
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                temp[i][j] = arr[i][j];
            }
        }
    }
}
 
void dfs(int level)
{
    if (level == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] > ans) {
                    ans = arr[i][j];
                }
            }
        }
        return;
    }
 
    int temp[21][21];                                    //백트래킹을 위해 temp배열 선언
 
    for (int i = 0; i < N; i++) {                        //지금 모습을 temp에 저장
        for (int j = 0; j < N; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    for (int k = 0; k < 4; k++) {
        turn(k);
        move();                                            //옮긴 후
        dfs(level + 1);                                    //다음으로 넘어갔다가
        for (int i = 0; i < N; i++) {                    //나올 때 원상 복구
            for (int j = 0; j < N; j++) {
                arr[i][j] = temp[i][j];
            }
        }
    }
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0);
 
    cout << ans;
}
cs
반응형
저작자표시 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24
[ 백준 ] 17143번 - 낚시왕 (C++)  (0) 2022.05.23
[ 백준 ] 16946번 - 벽 부수고 이동하기 4 (C++)  (0) 2022.05.22

+ Recent posts

티스토리툴바