본문 바로가기

공부/알고리즘 문제풀이

[SW Expert Academy]4301. 콩 많이 심기 [SW Expert Academy] 4301. 콩 많이 심기

반응형

4301. 콩 많이 심기 4301. 콩 많이 심기



누군가가 많이 떠오르는 문제입니다. 어? 왜 두 번 써지지???

누군가가 많이 떠오르는 문제입니다. 어? 왜 두 번 써지지???


SW Expert Academy의 문제는 저작권 때문에 링크로 대체하겠습니다!

SW Expert Academy의 문제는 저작권 때문에 링크로 대체하겠습니다!



어떻게 풀까?!

어떻게 풀까?!


처음에는 굉장히 복잡했지만, 단순하게 풀 수 있다는 것을 깨달았습니다...

처음에는 굉장히 복잡했지만, 단순하게 풀 수 있다는 것을 깨달았습니다...


그림으로 보시면 여러분도 금방 풀이법을 떠올리실 수 있을 것입니다!

그림으로 보시면 여러분도 금방 풀이법을 떠올리실 수 있을 것입니다!



 


자 우선, n = 3 , m = 4인 경우를 생각해보겠습니다.

자 우선, n = 3 , m = 4인 경우를 생각해보겠습니다.


모든 판에 콩을 심은 경우에서 시작합시다.

모든 판에 콩을 심은 경우에서 시작합시다.


 


이제 이차원 배열을 돌면서 길이가 2인 콩을 지워나가면 됩니다!

이제 이차원 배열을 돌면서 길이가 2인 콩을 지워나가면 됩니다!


 


요기도 지워버립시다!

요기도 지워버립시다!



참고로 콩이 심어져 있지 않으면, 지울 필요가 없으니 pass 합시다!

참고로 콩이 심어져 있지 않으면, 지울 필요가 없으니 pass 합시다!



n = 3, m = 4일 때 답은 6이 되겠군요!

n = 3, m = 4일 때 답은 6이 되겠군요!


코드

코드


 

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
#include<cstdio>
#include<cstring>
 
int map[1004][1004];
int dr[4= {2,0};
int dc[4= {0,2};
int n, m;
int res;
 
int main(){
    int t;
    scanf("%d\n"&t);
 
    for(int tc = 1; tc <= t; tc++){
        scanf("%d\n %d\n",&m, &n);
        memset(map, 0sizeof(map));
        res = n*m;
 
        for(int i = 2; i <= n + 1; i++){
            for(int j = 2; j <= m + 1; j++){
                if(map[i][j]) continue;
 
                for(int d = 0; d < 2; d++){
                    int nr = i + dr[d];
                    int nc = j + dc[d];
                    if(nr >= 2 && nr <= n + 1 && nc >= 2 && nc <= m + 1 && map[nr][nc] == 0) {
                        map[nr][nc] = 1;
                        res--;
                    }
                }
            }
        }
        printf("#%d %d\n", tc, res);
    }
    return 0;
}
cs

 

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
#include<cstdio>
#include<cstring>
 
int map[1004][1004];
int dr[4= {2,0};
int dc[4= {0,2};
int n, m;
int res;
 
int main(){
    int t;
    scanf("%d\n"&t);
 
    for(int tc = 1; tc <= t; tc++){
        scanf("%d\n %d\n",&m, &n);
        memset(map, 0sizeof(map));
        res = n*m;
 
        for(int i = 2; i <= n + 1; i++){
            for(int j = 2; j <= m + 1; j++){
                if(map[i][j]) continue;
 
                for(int d = 0; d < 2; d++){
                    int nr = i + dr[d];
                    int nc = j + dc[d];
                    if(nr >= 2 && nr <= n + 1 && nc >= 2 && nc <= m + 1 && map[nr][nc] == 0) {
                        map[nr][nc] = 1;
                        res--;
                    }
                }
            }
        }
        printf("#%d %d\n", tc, res);
    }
    return 0;
}
cs



여담

여담


for 문이 2개 입니다! 따라서 시간 복잡도도 이겠죠!


for 문이 2개 입니다! 따라서 시간 복잡도도 이겠죠!


반응형