[백준] 1292번 : 쉽게 푸는 문제 - C/C++

 

문제 자체는 특정 규칙을 따르는 수열을 생성한 뒤, 주어진 구간 합을 구하는 문제이다.

1,2,2,3,3,3,4,4,4,4,5,5,...

i라는 수가 i번 반복된다는 규칙을 가진다.

 

A,B 입력받고, 그에 해당하는 구간합 구하기

구간합 [a,b]는 sum += ary[i] 로 쉽게 구할 수 있다.

for(int i = a; i <= b; i++){
   sum += ary[i];
}

 

문제에서 제약조건을  정수 A, B(1 ≤ A ≤ B ≤ 1,000) 이렇게 걸어두었기 때문에

const로 NMAX를 선언하자.

const int NMAX = 1001;

1000으로 안 하고 왜 1001로 하나요?

--> 상관은 없다. (반복문 돌릴때 등호 쓰기 싫어서)

 

k는 현재 배열의 인덱스이다.

1로 초기화했었다.

for(int i = 0; i < NMAX; i++){
   for(int j = 1; j <= i; j++){
      ary[k] = i;
      if(k > 1000){
        break;
       }
       k++;
    }
}

 

숫자 i를 i번 더하는 코드를 추가했다.

1000개까지만 저장해야해서 if문으로 묶어주어야한다.

 

 

전체 코드

#include <iostream>

//쉽게 푸는 문제
using namespace std;

const int NMAX = 1001;

int main(){
    int a,b;
    cin >> a >> b;

    int ary[NMAX];
    int sum = 0, k = 1;

    for(int i = 0; i < NMAX; i++){
        for(int j = 1; j <= i; j++){
            ary[k] = i;
            if(k > 1000){
                break;
            }
            k++;
        }
    }
    for(int i = a; i <= b; i++){
        sum += ary[i];
    }
    cout << sum << '\n';
}

 

 

브론즈1의 문제였다.

근데 이 문제는 부분 합(구간 합)으로도 풀 수 있는 문제였다.

지난 글에서도 설명했지만,,, 나는 부분 합 문제가 너무 어렵다.

부분 합을 이용하지 않고 문제를 풀 수 있나? 하고 봤는데 풀려서.. 그냥 제출했다.

이건 반복문도 적게 돌기 때문에 시간초과가 나지 않았다.

숫자가 더 커지면 prefix sum을 이용하는 것이 시간복잡도 측면에서 좋다고 한다..

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️