[백준 BOJ] 1292번 쉽게 푸는 문제 (C언어)

문제 설명

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

1292번: 쉽게 푸는 문제

 

접근 방법 - 정말 "나름 가볍게" 풀 수 있는 수학적 사고 문제

백준의 1292번 문제는 단순 수학적 사고력을 요구하는 문제이다.

문제의 범위가 비양심적으로 방대했다면 어려웠을 수도 있지만, 그렇지는 않아서 무난하게 풀 수 있었다.

필자는 아래의 규칙을 찾아내고 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

밑의 후기도 한번 참고해보길 바란다.

 

필자가 이용한 규칙

(배열 번호 i인 배열 값 : cnt)

배열 번호 0인 배열 값 : 1 (sum = 1)

배열 번호 1, 2인 배열 값 : 2 (sum = 3)

배열 번호, 3, 4, 5인 배열 값 : 3 (sum = 6)

...

(sum: 출현한 cnt의 총합)

 

이 규칙대로라면, cnt가 1씩 증가하며 배열 값을 채우되,

배열 번호가 여태 출현한 cnt의 총합인 sum과 같을 때엔 cnt를 1 증가하게끔 하면 문제를 원활히 해결할 수 있다.

아래의 코드 실행 순서도 함께 참조해보길 바란다.

 

코드의 실행 순서

1) 배열 크기가 1000인 배열을 선언한 뒤, 각 자리에 맞게끔 초기화하기

cnt를 1씩 증가하며 각각 알맞은 배열 값을 채운다. (cnt가 1 증가하는 즉시 0으로 초기화된 sum에 cnt값 더하기)

만약 배열 번호 i가 sum과 같아지면, cnt를 1 증가한 뒤 배열 값 채우기를 연이어 실행한다.

 

2) 정답에서 요구하는 합을 구하기 위해 배열 범위를 입력받기

 

3) 1)에서 초기화한 배열에서 선택된 배열 범위의 배열 값 총합 구하기

 

4) 총합을 출력한 뒤 실행 종료한다.

 

후기

필자는 위의 코드 설명에 나온 대로, 배열 전체를 미리 초기화해둔 뒤 정답을 구해냈다. 그야말로 무식한 방법. (...)

배열 범위가 작은 편이어서 가능했던 방법이지, 그게 아니었다면 자칫 시간 초과가 걸렸을 것이다.

이 문제는 반복문의 실행을 줄이는 방법으로, 추후에 따로 다시 풀어보고자 한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>

//백준 1292번 코드
int arr[1000];
int main() {
	int cnt = 0;
	int sum = 0;
	int i = 0;
	while (i < 1000) {
		cnt++;
		sum += cnt;
		while (i < sum) {
			arr[i] = cnt;
			i++;
		}
	}

	int a, b;
	scanf("%d %d", &a, &b);
	sum = 0;
	for (i = a-1; i <= b-1; i++) {
		sum += arr[i];
	}
	printf("%d", sum);
}

 

제출 결과

(2021.12.13 백준 1292번 제출 결과)

(그나저나 이게 실버 문제라니)