[알고리즘 1단계] 태민이의 취미

[출처 : Goorm 사이트 - Yun Goon]

문제

태민이는 주사위를 수집하는 취미를 가지고 있습니다. 주사위의 모양과 색깔은 각기 다르며, 크기 또한 다릅니다. 태민이는 지금까지 모은 N개의 주사위가 너무 난잡하게 보관해놓고 있어서 정리를 결심했습니다. 그래서 우선 N개의 주사위를 크기 순서대로 정리해보려고 마음먹었습니다.

그렇게 주사위를 순서대로 정렬시켜보니 각 변의 길이가 1부터 N까지 모두 있는 것을 알게 되었습니다. 이 사실이 매우 신기했던 태민이는 이 주사위들의 부피의 합은 어떻게 될지 궁금해졌습니다. 태민이가 현재 가지고 있는 모든 주사위의 부피의 합은 얼마일까요? 태민이의 궁금증을 풀어주세요!

 

예시

 

---

풀이 (의식의 흐름)

1. 입력 받아야 할 것. - n개의 주사위, 크기는 1~n까지

unsigned int sum=0;

정수형 최대값 정리

​

3. 부피의 합 계산

for(int i=1; i<=length; i++){

     sum += i*i*i;

     }

 

2. 출력할 것. sum

=> 값이 커지자 fail이 뜬다.

​timeout이 뜨는 걸 보니, 단순 반복계산을 하면 안된다는 걸 깨달았다.

(입력하는 size가 커지면 연산량이 기하급수적으로 증가 O(n^3) 한다!)

 

3. 공식 구해보자

입력-출력=출력 값 분석

1-1(=1*1*1) = 1^2

2-9(=1*1*1+2*2*2)=3^2 +2

3-36=2^2+3*2=6^2 +3

4-100=2^2+5^2=10^2 +4

5-225=3^2*5^2=15^2 +5

6-441=3^2*7^2=21^2 +6

7-784=28^2 +7

----정말 나만 알아볼 수 있게 적었다..ㅎ.----

나열해놓고 보니 결국 수열 일반항 구하는 문제였다.

size가 n 일 때= (1부터 n까지의 합)^2

sum = ((n+1)*n/2)^2

​

역시 알고리즘 문제를 풀려면 등차, 등비, 계차수열 등등 한번 복습해야 겠다..

 

#include <stdio.h>
int main() {
  unsigned long long size = 0;
  unsigned long long sum=0; //정수 사이즈 최대로 해주었다.
  
  scanf("%llu", &size);
  sum = (size+1)*size/2*(size+1)*size/2;
  
  printf("%llu", sum%1000000007);
  return 0;
}

결과

띠용?

파이썬은 long형을 사용하면 메모리가 허용하는 한 표현 범위가 무제한인 반면에 C는 제한이 있어서 범위가 커지면 오버플로우 된다.
나는 C로 작성했기에 sum값이 (2^64)-1(unsigned long long 의 최대값)이상이 되는 4번 예제 이후로는 오버플로우로 인해 fail이 떴다.

 

결론 : 수열 복습하기

 

 

---

* 개인적인 공부 목적으로 게시한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 -  https://level.goorm.io/exam/49094/태민이의-취미/quiz/1