[코딩 테스트] 소프티어(Softeer) 연습 문제 - 지도 자동 구축

코딩 테스트를 위한 소프티어(Softeer) 연습 문제 중 지도 자동 구축 문제를 풀어보고 리뷰해 본다.

 

연습 문제 - 지도 자동 구축

• 난이도 : level 2
• 정답률 : 62%

https://softeer.ai/practice/info.do?idx=1&eid=413 

Softeer

 

문제 해설

지도 자동 구축이라는 문제 컨셉이다. 정사각형이 있고 각 꼭짓점에 4개의 점이 있다. 여기서 차수가 늘어갈수록 점이 추가되는 문제이다. 추가되는 점은 2가지이다.

예제 그림

• 정사각형의 각 변의 중앙에 점을 하나 추가한다.
• 정사각형의 중심에 점을 하나 추가한다.

이렇게 패턴에 따라 증가하면

4 -> 9 -> 25 -> 81... 이렇게 증가하게 될 것이다. 이 때 각 차수에 따른 규칙을 찾는 문제이다.

우선 정사각형이라서 각 차수에 따라 어떤 수의 제곱이 된다는 것을 파악했다. 즉 2의 제곱, 3의 제곱, 5의 제곱, 9의 제곱의 패턴으로 늘어나는 것을 파악했고 그다음 2 -> 3 -> 5 -> 9의 차이가 2의 배수만큼 증가한다는 것을 알았다. 즉 직전 차수의 결괏값에 다가 그 차수만큼의 2의 배수를 더하면 된다.

내가 생각한 방법은 심플하면서 순차적으로 해결할 수 있는 방법이었다.

• 입력받은 차수까지 2의 배수를 기록하는 배열을 하나 만든다.
• 결과 배열을 만들고 (최초의 값은 넣어두고) 직전의 값과 2의 배수의 값을 더한 값을 현재 값에 저장한다.
• 최종 타겟 차수의 결과 배열에 제곱의 값을 반환한다.

 

제약조건

1 ≤ N ≤ 15

 

입력

1

 

출력

9

최초 4에서 1 차수 진행된 값은 9가 된다.

 

코드

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int calculate(int n) {
	//arr       1    2    4    8
	//res     2 -> 3 -> 5 -> 9 -> 17
	//return  *2   *3   *5   *9
	int arr[17];
	int res[17];
	int base = 1;
	arr[0] = 1;
	arr[1] = 1;
	res[0] = 1;
	for (int i = 2; i <= n; i++) {
		base = base*2;
		arr[i] = base;
	}
	for (int i = 1; i <= n; i++) {
		res[i] = arr[i-1] + res[i-1];
	}

	return res[n] * res[n];
}
int main(int argc, char** argv)
{
	int N;
	int result;
	cin >> N;

	result = calculate(N+1);

	cout << result;

	return 0;
}

 

결론

순차적으로 단순하게 해결하면 매우 쉽지만 효과적으로 깔끔하게 구현하려고 하면 조금 더 생각이 필요한 문제 같아 보인다.