[백준] 2903번 - 중앙 이동 알고리즘 (node.js)

 

 

 

 

반응형

 

[백준] 2903번 - 중앙 이동 알고리즘 (node.js)

나의 머리가 굳어 간다고 생각이 들게한 문제..

구할수 있을것 같았는데 1시간이 다되가도록 답을 내지못했다.

그래서 다른 분들은 어떻게 풀었는지 살펴보고 블로그에 올리려한다.

 

 

 

 

 

문제

 

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다.

실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다.

그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

 

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

 

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다.

이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

 

초기 상태 - 점 4개	1번 - 점 9개	2번 - 25개

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다.

메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다.

과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

 

 

출력

 

첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다.

 

 

 

문제풀이

 

주어진 도형이 정사각형이기 때문에 아래와 같은 식이 성립합니다.

한 줄의 사각형의 갯수 = 2 ** n
한 줄의 꼭짓점의 갯수 = 한 줄의 사각형의 갯수 + 1 = 2 ** n + 1
--------------------------------------------
총 꼭짓점의 갯수 = 한 줄의 꼭짓점의 갯수 ** 2 = (2 ** n + 1) ** 2

 

 

const fs = require("fs");
const input = +fs.readFileSync(0, 'utf-8').toString().trim();

const result = (2 ** input + 1) ** 2;
console.log(result);

 

 

 

 

다른 방식

let input = require('fs').readFileSync('/dev/stdin').toString().trim();
let N = parseInt(input);
let dot = 2;
for(let i=0; i<N; i++){
    dot += Math.pow(2, i);
};
console.log(Math.pow(dot, 2))

 

단계마다 한변에 새로 생기는 점의 갯수가 2의 제곱수로 증가하므로 한 변 위의 점의 갯수(dot)를 먼저 구하고,

dot를 제곱하여 점의 총 갯수를 출력하여 풀이하였다

 

 

 

Math.pow()

**Math.pow()**함수는base^exponent처럼 base 에 exponent를 제곱한 값을 반환합니다.

Math.pow(base, exponent);

 

• base : 밑 값
• exponent : 밑을 제곱하기 사용되는 지수
• 반환값 : 주어진 밑값을 주어진 지수 값으로 거듭제곱한 숫자 값

예시

console.log(Math.pow(7, 3));
// Expected output: 343

console.log(Math.pow(4, 0.5));
// Expected output: 2

console.log(Math.pow(7, -2));
// Expected output: 0.02040816326530612
//                  (1/49)

console.log(Math.pow(-7, 0.5));
// Expected output: NaN

 

 

 

 

 

 

참조!

https://arnopark.tistory.com/639

[백준JS] 2903. 중앙 이동 알고리즘

https://velog.io/@anjin7/%EB%B0%B1%EC%A4%80-2903-%EC%A4%91%EC%95%99-%EC%9D%B4%EB%8F%99-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-js

[ 백준 ] 2903 중앙 이동 알고리즘 [ js ]