이 영역을 누르면 첫 페이지로 이동
Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

페이지 맨 위로 올라가기

Stranger's LAB

프로그래밍과 관련하여 다양한 알고리즘 문제를 풀어보고, 프로그래밍 언어를 이해해 볼 수 있도록 돕고자 만든 블로그 입니다.

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

  • 2021.03.26 20:54
  • C++ - 백준 [BAEK JOON]/반복문
글 작성자: ST_
728x90





 
www.acmicpc.net/problem/8393

 

8393번: 합

n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

 

 

 

 

 

 





  • 문제

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 





  • 알고리즘 [접근 방법]

 



 

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

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

 

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

st-lab.tistory.com/228

 

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

www.acmicpc.net/problem/2739 2739번: 구구단 N을 입력받은 뒤, 구구단 N단을 출력하는 프로그램을 작성하시오. 출력 형식에 맞춰서 출력하면 된다. www.acmicpc.net 문제 for문의 가장 기초적인 문제다! 알고리

st-lab.tistory.com

 

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

 

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 카테고리에서 특히 유용하다.

 

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

 

 



저작자표시 비영리 변경금지 (새창열림)

'C++ - 백준 [BAEK JOON] > 반복문' 카테고리의 다른 글

[백준] 11022번 : A+B - 8 - [C++]  (0) 2021.05.02
[백준] 11021번 : A+B - 7 - [C++]  (0) 2021.04.26
[백준] 15552번 : 빠른 A+B - [C++]  (6) 2021.03.28
[백준] 10950번 : A+B - 3 - [C++]  (5) 2021.03.22
[백준] 2739번 : 구구단 - [C++]  (0) 2021.03.19

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 11021번 : A+B - 7 - [C++]

    [백준] 11021번 : A+B - 7 - [C++]

    2021.04.26
  • [백준] 15552번 : 빠른 A+B - [C++]

    [백준] 15552번 : 빠른 A+B - [C++]

    2021.03.28
  • [백준] 10950번 : A+B - 3 - [C++]

    [백준] 10950번 : A+B - 3 - [C++]

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

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

    2021.03.19
다른 글 더 둘러보기

정보

Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

  • Stranger's LAB의 첫 페이지로 이동

검색

나의 외부 링크

  • st-github

공지사항

  • 공지 - 블로그 사용 설명서

메뉴

  • 홈
  • 방명록

카테고리

  • 전체 카테고리 (267)
    • Java (5)
    • JAVA - 백준 [BAEK JOON] (177)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (10)
      • 기본 수학 1 (8)
      • 기본 수학 2 (6)
      • 2차원 배열 (0)
      • 정렬 (10)
      • 재귀 (4)
      • 브루트 포스 (5)
      • 집합과 맵 (0)
      • 기하 1 (5)
      • 정수론 및 조합론 (12)
      • 백트래킹 (8)
      • 동적 계획법 1 (15)
      • 누적 합 (0)
      • 그리디 알고리즘 (5)
      • 스택 (5)
      • 큐, 덱 (7)
      • 분할 정복 (9)
      • 이분 탐색 (7)
      • 기타 문제 (17)
      • 별 찍기 문제 모음 (2)
    • C++ - 백준 [BAEK JOON] (46)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (0)
      • 기타 문제 (4)
    • 자료구조 (18)
      • Java (18)
    • 알고리즘 (11)
      • Java (11)
    • 프로그래밍 기초 (6)
    • 이모저모 (2)
    • 일상의 글 (2)

최근 글

정보

ST_의 Stranger's LAB

Stranger's LAB

ST_

블로그 구독하기

  • 구독하기
  • 네이버 이웃 맺기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © ST_.

티스토리툴바