[BOJ]1292 쉽게 푸는 문제(B1, C++)

📋 개요 

감잡기 문제를 풀면서 1주일간은 브1에서 실3까지 풀고 있다. 이전에 임시반장 정하기 문제를 풀었다. 2시간을 다 써서 브1따위에 자존심이 완전히 구겨져버렸지만, 그래도 해야함을 알고 있기에 정진 하고 있다.

2024.02.21 - [Algorithm/Problem] - [BOJ]1268 임시 반장 정하기 (B1, C++)

[BOJ]1268 임시 반장 정하기 (B1, C++)

 

이번 문제는 어렵지 않았다. 쉽다는 표현이 맞을지도 모르겠다. 범위를 알고 시간복잡도를 계산할줄 알면 쉽게 해결할 수 있다.

---

🧩 문제

https://www.acmicpc.net/problem/1292

1292번: 쉽게 푸는 문제

📝  제한 사항 및 형식 

제한시간 2초

메모리 제한 128MB

📥 입력	📤 출력
첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.	첫 줄에 구간에 속하는 숫자의 합을 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	3 7	15

 

🥕  내 코드가 정답코드

---

📖  해설 및 느낀점

# 해설

문제에서 A,B의 범위가 1부터 1000이였다.

  for (int i = 0; i <= 1000; i++)
    {
        for (int j = 0; j < i; j++)
        {
            v.push_back(i);
        }
    }

1000을 n이라고 가정하고 시간복잡도를 구해보자. 시간제한은 2초이다.

바깥쪽 반복문은 N번 반복을 하게되고 안쪽 반복은 i의 값에 따라 반복횟수가 변하게된다.

i는 1부터 N까지 변하고, 안쪽 반복문은 해당하는 i만큼 반복하여 N+N+1+N+3 ... 이렇게 반복됨으로 상수를 버려 O(N)이된다.

 

결국 1000까지니깐 1000번만 연산을 하면된다는 것이다. 시간제한이 2초니깐 여유롭겠다고 생각했고, 무식하게 vector에 모든 배열을 다 집어넣고 풀이했다.

 

다른 사람들의 풀이를 보니깐 쪼개서 연산하고 하던데, 숫자가 커지면 그대로 되겠지만 제한에 맞춰 적절하게 풀이했다고 생각했다. (아래는 vector에 관한 설명이다.

2024.01.23 - [Language/C++] - [C++] STL (Standard Template Library) 1편 - Container

[C++] STL (Standard Template Library) 1편 - Container

 

---

30분만에 이 문제를 풀 수 있었다. 처음에는 시간제한을 확인하지 않고 1000개를 어떻게 다 계산해, 시간 초과 나는거 아니야? 라고 걱정했지만 항상 구현문제는 코드를 작성하기전 미리 사전에 걱정하는 것은 큰 도음이 되지 않는다.

전체적인 알고리즘을 구상하고 시간복잡도나 공간복잡도를 해결할 수 있는 방법에 대해서 고민을 해야할거 같다. 마음 먹은대로 가즈아~