[백준] 8393번 : 합 - [C++]

 
www.acmicpc.net/problem/8393

8393번: 합

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

이 번 문제 또한 그리 어렵지 않은 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

대부분 카테고리별로 순차적으로 풀어오셨다면 이 번 문제 또한 그리 어렵지 않게 풀었을 것이다.

n이 주어졌을 때 1부터 n까지의 합을 구하면 되는 문제라 반복문으로 1부터 n까지 반복하면서 누적 합을 구하면 된다.

 

만약 반복문에 대해 잘 모르신다면 다음 글을 보고 오면 도움이 될 것이다.

st-lab.tistory.com/228

[백준] 2739번 : 구구단 - [C++]

 

알고리즘 자체는 다음과 같이 풀이할 수 있다.

 

int sum = 0;
for(int i = 1; i <= n; i++) {
	sum = sum + i;
}
cout << sum;

 

 

 

이렇게 푸는 것이 문제의 취지에는 맞지만, 더욱 우리는 깔쌈한 코드를 만들 수 있다.

 

수학적으로 접근하는 것이다. 고등 수학 과정을 거치셨다면 다들 알 법한 수열의 합 공식을 이용하는 것이다.

 

k=1부터 n까지의 합 공식이다.

 

즉, n을 입력 받았다면 n(n + 1) / 2를 계산하여 출력해도 된다는 말이다. (당연하게도 n 또는 n+1 중 하나는 반드시 짝수이기 때문에 2로 반드시 나누어 떨어진다.

 

즉, 아래와 같이 풀 수도 있다.

 

cout << n * (n + 1) / 2;

 

더욱 깔쌈해진 코드다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

 

위 알고리즘에서 설명한 반복문을 이용한 풀이와 수식을 이용한 풀이 두 가지를 이용하여 풀이해보도록 하겠다.

 

 

1. 반복문

2. 수식

 

 

 

 

---

• 풀이

- 방법 1 : [반복문]

 

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	int n;
	int sum = 0;
	cin >> n;

	for (int i = 0; i <= n; i++) {
		sum = sum + i;
	}
	cout << sum;
	return 0;
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

 

 

---

- 방법 2 : [수식]

 

 

 

앞서 설명한 수식으로 접근하는 방법이다.

 

 

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	int n;
	cin >> n;
	cout << n * (n + 1) / 2;
	return 0;
}

 

 

 

코드가 훨씬 간결하고 깔끔해진 걸 볼 수 있다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 27717288  -  방법 2 : 수식

채점 번호 : 27717283  -  방법 1 : 반복문

 

 

 

성능상 차이를 보이진 않은듯 하다.

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다. 

 

필자가 왜 수식 풀이도 보여줬냐면 앞으로 이렇게 수학적으로 수식화 하여 풀이 할 일이 많기 때문이다.

나중에 좀 더 어려운 알고리즘으로 가게 되면 반복하는 양에 따라 성능차이가 많이 차이나게 되는데 수식으로 잘 정리할 수 있다면 충분히 반복하지 않고도 풀이 할 수 있다는 장점이 있다. 이 부분은 기본 수학 1, 2 카테고리에서 특히 유용하다.

 

또한 후에 재귀 혹은 이를 이용한 동적계획법 같은 문제를 다룰 때 점화식을 세울줄 알면 문제를 훨씬 빠르게 풀 수 있기 때문에 이러한 수학적 지식을 갖고있으면 매우 편리하니 만약 수학적으로 풀이 할 수 있다면 한 번 쯤은 도전해보면서 연습해도 좋을 것이다.