[BOJ] 백준 1292 쉽게 푸는 문제

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

Approach

for 문을 연습하기 좋은 문제라고 생각한다.

주어지는 A, B의 범위가 1000 이하이므로

배열 크기 = 1000으로 만들어서

arr = [1 2 2 3 3 3 4 4 4 4 ...45, 45]와 같이 원소를 채워넣는다.

 

입력으로 받은 구간 [A, B] 합을 for문으로 탐색한 후 출력한다.

O(N)의 시간으로 실행시간은 충분하다

▶ 알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? 

▶ 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기  

 

C++

#include <stdio.h>

const int MAX_N = 1e3 + 5;
int arr[MAX_N];
int A, B, ans, cnt, val;

int main() 
{
	// freopen("input.txt", "r", stdin);
	scanf("%d %d", &A, &B);

	cnt = val = 1;
	while (cnt <= 1000) // 배열에 1000개의 데이터를 채운다.
	{
		for (int i = 1; i <= val; i++)
		{
			arr[cnt++] = val;
			if (cnt > 1000) break;
		}
		val++;
	}

	// 구간합
	for (int i = A; i <= B; i++) {
		ans += arr[i];
	}

	printf("%d\n", ans);
}

 

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 특정범위를 입력 받는다.
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());
        
        int[] arr = new int[1001];
        
        int idx = 1;
        int cnt = 1;
        // 전체구간의 숫자를 할당한다.
        while(true) {
        	
        	// 1은 한 개, 2는 2개, 3은 3개씩...
        	for(int i=0; i<cnt; i++) {
        		// 숫자 할당
        		arr[idx++] = cnt;
        		
        		// 모든 배열의 숫자의 배정이 끝났다면...
        		if(idx > 1000) {
        			
        			int sum = 0;
        			// 특정 구간의 합을 구한 후, 출력한다.
        			for(int j=A; j<=B; j++) {
        				sum += arr[j];
        			}
        			System.out.println(sum);
        			return;
        		}
        	}
        	cnt++;
        }
        

        
    }
}