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

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

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 2903번 문제 - 중앙 이동 알고리즘 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 2903

 

백준 2903번 문제 중앙 이동 알고리즘 보러가기

 

반응형

 

문제 해석

 

문제에서 원하는 값은 점의 총개수입니다.

중복되는 점은 한번만 저장한다는 말이 문제에 등장하기 때문에 "특별한 과정을 풀이에 넣어야 하나?"라는 생각이

들기 마련입니다. 하지만 문제를 바라보는 시점을 살짝만 돌려보면 정말 정말 단순하게 해결이 가능해집니다.

힌트 : 우리가 평상시에 사각형으로 정렬되어 있는 물건의 개수를 셀 때 어떻게 하나요??

 

풀이

 

n = int(input())

a = 2
for _ in range(n):
    a = 2 * a - 1

print(a * a)

 

풀이 해석 및 팁

 

문제를 보고 천천히 생각해 보니 단순히 한 변에 존재하는 점의 개수만 구하면 된다라는 결론이 나왔습니다.

처음에는 2개 다음 차례엔 3개 그 다음 차례엔 5개 또 그 다음 차례엔 9개 이렇게 늘어나는 상황에서

규칙성을 찾아보니 A = 2 * A - 1 가 반복되는 것을 확인할 수 있었습니다.

몇 번의 과정을 거칠지를 입력값으로 받게 되면 그 횟수만큼 위 식을 반복해서 한 변에 존재하는 점의 개수를

찾아내고 제곱해서 출력하면 문제가 해결됩니다.

---

여기까지 백준 2903번 중앙 이동 알고리즘 문제 풀이였습니다.

 

이번 문제는 문제의 이름만으로 뭔가 어려운 방식을 사용해야하나? 라는 인상을 주는데요.

 

사실상 정말 쉽게 풀 수 있는 문제였습니다.

 

알고리즘 문제뿐만 아니라 인생을 살아가면서 마주하게 되는 문제들도

 

여러 관점으로 바라보면 생각하지못한 해결법 또는 손쉬운 해결법을 얻을 수 있을 겁니다.

 

생각의 전환이 도움이 되었던 문제였네요.

 

감사합니다.