728x90
1. 문제
- 문제 링크 : Lv2. 지도 자동 구축
- 주제 : Math
2. 풀이 과정 및 정리
내가 이 문제에서 핵심으로 잡은 것은 정사각형의 한 변에 포함되어 있는 점의 개수이다.
이 문제는 정사각형의 중앙에 점을 추가하여 작은 정사각형이 또 생겨난다.
그러므로 단계가 올라갈수록 한 변에 포함되어 있는 점의 개수가 증가한다.
위의 그림은 1단계에서 2단계로 올라갈 때 점의 개수 변화를 나타낸 그림이다.
이 그림을 통해 특징을 생각해보면
- 두 점 사이에 1개의 점이 추가된다. 즉, 한 변에 점 n개가 있을 경우 n-1개의 점이 추가된다.
- 모든 점의 개수는 한 변의 개수의 제곱이다. 즉, n의 제곱이다.
그러므로 나는 한 변의 점의 개수가 어떻게 변하는지에 집중했다.
1단계 → 2단계
기본 3개의 점이 존재한다.
3 - 1 = 2개의 점을 추가할 수 있다. → 2^1
2단계 → 3단계
기존의 3 + 2 = 5개의 점이 존재한다.
5 - 1 = 4개의 점을 추가할 수 있다. → 2^2
3단계 → 4단계
기본으로 5 + 4 = 9개의 점이 존재한다.
9 - 1 = 8개의 점을 추가할 수 있다. → 2^3
위와 같이 단계가 1씩 증가할수록 추가되는 점의 개수는 2, 4, 8 ... 2의 제곱으로 증가한다.
다만 이는 앞 단계 개수에서 증가한다는 것을 기억해야한다.
그러므로 현재 단계(n)에서 기본적으로 가지는 점의 개수는 [(n-1)단계의 점의 개수 + 추가할 점의 개수] 이다.
→ 최소 개수부터 단계별 추가할 점의 개수를 계속해서 더해주어야 한다.
n은 최소 1이므로 한 변의 최소 점의 개수(a)는 3이다.
더해주어야할 값은 2의 제곱으로 n-1 제곱까지 더해주면 된다.
int a = 3; //한 변의 점 개수
for(int i = 1; i < n; i++) {
a += (int)Math.pow(2, i);
}
3. 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int a = 3; //한 변의 점 개수
for(int i = 1; i < n; i++) {
a += (int)Math.pow(2, i);
}
bw.write(a * a + "");
bw.flush();
bw.close();
}
}
728x90
'ProgramSolve > Softeer' 카테고리의 다른 글
[Softeer] Lv3. GINI야 도와줘 (Java) (0) | 2024.02.22 |
---|---|
[Softeer] Lv3. 비밀메뉴2 (Java) (0) | 2024.02.20 |
[Softeer] Lv3. 성적평가 (Java) (0) | 2024.02.04 |
[Softeer] Lv3. 순서대로 방문하기 (Java) (2) | 2024.02.03 |
[Softeer] Lv3. 자동차 테스트 (Java) (0) | 2024.02.02 |