๋ฌธ์ œ

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

์„ค๋ช…

์ด๋ฌธ์ œ๋„ ์ „์— ํ’€์—ˆ๋˜ ์†Œ์ˆ˜ ๋ฌธ์ œ์™€ ์œ ์‚ฌํ•˜๊ฒŒ ์ผ๋‹จ ํ•ด๋‹นํ•˜์ง€ ์•Š๋Š” ์ˆ˜๋ฅผ ๊ฑฐ๋ฅด๊ณ  ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ฝ”๋“œ๋ฅผ ์งฐ๊ธฐ๋•Œ๋ฌธ์— 10001 ์˜ ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์„ ๋งŒ๋“ค๊ณ  ๋งž๋Š”๊ฒƒ ์•„๋‹Œ๊ฒƒ์„ ๋‹ค ํ‘œ์‹œํ•˜์—ฌ ์•„๋‹Œ๊ฒƒ์„ ๋”ฐ๋กœ ๋‹ค์‹œ for๋ฌธ์œผ๋กœ ์ถœ๋ ฅํ•˜๋„๋ก ํ•˜์˜€๋‹ค. ์‚ฌ์‹ค ์ž๋ฆฟ์ˆ˜๋ฅผ ๋ถ„๋ฆฌํ•˜๋Š” ๋ถ€๋ถ„๋•Œ๋ฌธ์— ๊ธธ์ด๊ฐ€ ๋”๊ธธ์–ด์กŒ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ๋” ์ค„์ด๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ์„์ง€๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ๋‹ค. ์ผ๋‹จ ๋งž์ถ”๊ธด ํ–ˆ์œผ๋‚˜ ์•ฝ๊ฐ„ ํ•˜๋“œ์ฝ”๋”ฉ์„ ํ–ˆ๋‹ค๋Š” ๋Š๋‚Œ์ด ๋“œ๋Š”๊ฑด ์–ด์ฉ”์ˆ˜ ์—†๋Š” ๋“ฏ ํ•˜๋‹ค.

์ฝ”๋“œ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int arr[10001];
	for (int i = 0; i <= 10000; i++)
		arr[i] = 0;
	for (int i = 1; i <= 10000; i++)
	{
		int line = 0,num[5];
		if (i < 10)//1์˜์ž๋ฆฌ ์ˆ˜
		{
			line = 1;
			num[0] = i;
		}
		else if (i < 100) //10์˜ ์ž๋ฆฌ ์ˆ˜
		{
			line = 2;
			num[0] = i % 10;
			num[1] = i/10;
		}
		else if (i < 1000) // 100์˜ ์ž๋ฆฌ ์ˆ˜
		{
			line = 3;
			num[2] = i / 100;
			num[1] = (i - (num[2] * 100)) / 10;
			num[0] = (i - (num[2] * 100)) % 10;
		}
		else if (i < 10000) // 1000์˜ ์ž๋ฆฌ ์ˆ˜
		{
			line = 4;
			num[0] = i % 10;
			num[1] = (i % 100) / 10;
			num[2] = (i % 1000) / 100;
			num[3] = i / 1000;
		}
		else // 10000
		{
			line = 5;
			num[4] = 1;
			for (int j = 0; j <= 3; j++)
				num[j] = 0;
		}
		int temp=0;
		temp += i;
		for (int j = 0; j < line; j++)
			temp += num[j];
		if (temp <= 10000)
			arr[temp - 1] = 1;
	}
	for (int i = 0; i <10000; i++)
	{
		if (arr[i] == 0)
			printf("%d\n", i + 1);
	}
	return 0;
}