JArchive 프로그래밍 일기

문제 

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요.

만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다.

출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.

1 2 2 3 2 4 2 4 와 같이 출력한다.

입력설명 

첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.

출력설명

첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다

풀이 

이중 반복문을 이용해서 숫자 마다의 약수를 구하려고 했었다. 

하지만 그렇게 하면 시간초과가 난다. 

그래서 약수의 개수를 for문을 순회할 때마다 +1 해주는 방식이 필요하다. 

"1을 약수로 갖는 숫자들은 어떤 숫자들일까?"
"1의 배수들이다."

"2을 약수로 갖는 숫자들은 어떤 숫자들일까?"
"2의 배수들이다."

2의 배수들은 2를 약수로 갖는다. 

이 점을 이용한 것이다. 

1은 모든 수의 약수이므로 배열 모든 칸에 +1을 해준다. 

2는 모든 짝수 들의 약수이므로 2의 배수에 해당하는 칸에 +1을 해준다. 

. . . 

내부 for문을 이렇게 구현한다. 즉, j는 i로 시작하되, i의 배수이니까 j는 j+i만큼 커지면서 배열을 건너뛰어가면서 배수를 인덱싱한다. 

궁금한 점 

50001 크기의 int 배열 cnt는 지역변수 인 경우에 테스트케이스에서 fail이 난다. 

그런데 cnt가 전역변수 인 경우에는 테스트케이스를 전부 통과했다. 

그 차이가 뭔지 궁금했다. 

#include <stdio.h> 

int cnt[50001];

int main(int argc, char** argv) {
	
	//freopen("input.txt", "rt", stdin);
	int input=0, i=0, j=0;
	scanf("%d", &input);
	
	for(i=1; i<=input; i++){
		
		// i의 배수들을 +1 처리해준다. 
		// i를 약수로 갖는 숫자들을 찾는 것이다.  
		for(j=i; j<=input; j=j+i){
			cnt[j]++;
		}
	}
	
	for(i=1; i<=input; i++){
		printf("%d ", cnt[i]);
	} 

	return 0;
}

선생님이 답변을 달아주셨다. 

백준 괄호 문제 풀이  https://www.acmicpc.net/problem/9012

닫는 괄호로 시작하는 경우에 어떻게 할지 예외처리를 안넣어줘서 시간이 좀 걸렸다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>

using namespace std;

void check() {
	char stack[50] = {0, };
	int stack_idx = 0;

	char* inputStr = (char*)malloc(sizeof(char) * 50);
	scanf("%s", inputStr);

	int lenSize = strlen(inputStr);

	for (int i = 0; i < lenSize; i++) {
		if (0==i && ')' == inputStr[i]) { //닫는괄호로 시작함.
			printf("NO\n");
			free(inputStr);
			return;
		}
		else {
			if ('(' == inputStr[i]) { //스택에 여는괄호를 넣는다 
				stack[stack_idx] = '(';
				stack_idx++;
			}
			else if (')' == inputStr[i]) { // 닫는괄호 발견.
				if (0 < stack_idx) { // 스택에 여는괄호가 있다면, 하나 삭제.
					stack[stack_idx] = 0;
					stack_idx--;
				}
				else {
					// 여는 괄호 보다, 닫힌 괄호가 더 많음. 불완전.
					printf("NO\n");
					free(inputStr);

					return;
				}
			}
		}

	}

	//printf("stack_idx : %d", &stack_idx);

	if (0 == stack_idx) {
		printf("YES\n");

	}
	else {
		printf("NO\n");
	}

	free(inputStr);
	return;

}

int main() {

	// 반복 횟수 입력 받기
	int repeat = 0;

	scanf("%d", &repeat);

	while (repeat) {
		check();
		repeat--;
	}

	return 0;
}