[SWEA] 4301번 콩 많이 심기

4301번 콩 많이 심기

문제 링크

 

해결방법

조건에 맞게 구현하는 문제이다

 

 

⭐️ 솔루션 ⭐️

문제의 유형은 완전탐색처럼 보인다. 하지만 N≤10,000 이라는 조건으로 완전탐색은 불가능하다. 따라서 새로운 접근이 필요했다.

손으로 콩을 직접 심어보니, 5x3의 경우 아래와 같은 모형이 나왔다

	0	1	2	3	4	5
0	x	x			x	x
1		x	x			x
2			x	x		
3	x			x	x

그래서 전체 맵을 탐색했다

만약, 4방향에서 거리가 2인 노드에 콩이 모두 심어져있지 않다면, 콩을 심을 수 있는 곳이었다

따라서, O(N*M*4) 의 시간복잡도를 통해 문제를 해결할 수 있었다.

 

 

소스코드

문제 해결 시간 : 30m

메모리 : 16536 KB

시간 : 67 ms

#include <iostream>
#include <cstring>
#define MAX 1001
using namespace std;

int testcase;
int n,m,ans;
bool map[MAX][MAX];

int dx[4] = {0,0,2,-2};
int dy[4] = {2,-2,0,0};

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        cin >> m >> n;
        
        memset(map, false, sizeof(map));
        ans = 0;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                bool flag = true;
                
                for(int k=0; k<4; k++){
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    
                    if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
                    
                    if(map[nx][ny]){
                        flag = false;
                        break;
                    }
                }
                
                // 거리가 2인 노드에 콩이 안심어져있다면
                if(flag){
                    map[i][j] = true;
                    ans++;
                }
            }
        }
        
        cout << "#" << tc << " " << ans << "\n";
    }
    
    return 0;
}