관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [모의 SW 역량테스트] 홈 방범 서비스 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [모의 SW 역량테스트] 홈 방범 서비스 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 9. 29. 11:31


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

해답 코드 : 

 

#include<iostream>
#include <stdio.h>
#include<vector>
#define _CRT_SECURE_NO_WARNINGS

using namespace std;

int N, M;
int map[20][20];
int max_houses;

// number of houses
int house;
// 최대 potential K 값
int K;

typedef struct pos {
	int x;
	int y;
	int area;
} pos;

bool isRange(int x, int y) {

	if (x < 0 || x >= N || y < 0 || y >= N) {
		return false;
	}

	return true;
}


// for length k's area, get the number of houses dynamically
int greedy(pos dyna[][400], int cur_len) {

	int sum;
	int temp_x;
	int temp_y;


	int l_r, l_c, r_r, r_c;

	for (int i = 0; i < N*N; i++) {

		int temp = max_houses;
		temp_x = i / N;
		temp_y = i % N;
		sum = dyna[cur_len-1][i].area;


		int j = 1;

		if (isRange(temp_x-cur_len+1, temp_y) && map[temp_x-cur_len+1][temp_y] == 1) {
			sum++;
		}

		for (int k = temp_x - (cur_len - 2); k < temp_x; k++) {

			l_r = k; 
			r_r = k;
			l_c = temp_y - j; 
			r_c = temp_y + j;

			if (isRange(l_r, l_c) && map[l_r][l_c] == 1) {
				sum++;
			}

			if (isRange(r_r, r_c) && map[r_r][r_c] == 1) {
				sum++;
			}

			j++;

		}

		j = cur_len-1;

		for (int k = temp_x; k < temp_x + cur_len-1; k++) {

			l_r = k;
			r_r = k;
			l_c = temp_y - j;
			r_c = temp_y + j;

			if (isRange(l_r, l_c) && map[l_r][l_c] == 1) {
				sum++;
			}

			if (isRange(r_r, r_c) && map[r_r][r_c] == 1) {
				sum++;
			}

			j--;

		}

		if (isRange(temp_x+cur_len-1, temp_y) && map[temp_x+cur_len-1][temp_y] == 1) {
			sum++;
		}

		dyna[cur_len][i].area = sum;

		if (sum * M >= cur_len * cur_len + (cur_len - 1) * (cur_len - 1)) {
			if (sum > max_houses) max_houses = sum;
		}

		
	}




	return 0;
}



int main(int argc, char** argv)
{
	int test_case;
	int T;
	/*
	   아래의 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	   앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
	   //여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
	   freopen 함수를 이용하면 이후 cin 을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
	   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 함수를 사용하셔도 좋습니다.
	   freopen 함수를 사용하기 위해서는 #include <cstdio>, 혹은 #include <stdio.h> 가 필요합니다.
	   단, 채점을 위해 코드를 제출하실 때에는 반드시 freopen 함수를 지우거나 주석 처리 하셔야 합니다.
	*/
	
	//FILE* fp;
	//freopen_s(&fp, "sample_input.txt", "r", stdin);
	
	cin >> T;

	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N >> M;

		max_houses = 1;
		house = 0;
		K = 0;

		// dynamically store the result
		pos dyna[30][400];


		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];

				dyna[1][i * N + j].area = 0;

				if (map[i][j] == 1) {
					dyna[1][i*N + j].area = 1;
					house++;
				}

			}
		}

		
		// 가능한 최대 영역 k의 값을 구함
		for (int i = 0; i < 30; i++) {
			
			if (house * M < i * i + (i-1) * (i-1)) {
				K = i - 1;
				break;
			}
		
		}
		

		for (int i = 2; i <= K; i++) {
			greedy(dyna, i);
		}


		cout << "#" << test_case << " " << max_houses << "\n";


	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

0 Comments
댓글쓰기 폼