Bin_S+StudyRoom

• 문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

• 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

• 출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

• 예제 입력

4
3 5 2 7

4
9 5 4 8

• 예제 출력

5 7 7 -1

-1 8 8 -1

• 접근방식

짝 짓기 문제는 스택을 사용, 오큰수가 나올때 까지 푸쉬하고 나온다면 pop 하면서 오큰수를 만듬

• 코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <string.h>

using namespace std;

int n, number[1000004], ret[1000004];
stack<int> stk;

int main()
{
	cin >> n;

	memset(ret, -1, sizeof(ret));

	for (int i = 0; i < n; i++)
	{
		cin >> number[i];
		while (stk.size() && number[stk.top()] < number[i]) // 스택이 존재하고 스택의 탑보다 큰 경우 오큰수 결정
		{
			ret[stk.top()] = number[i]; 
			stk.pop();
		}
		stk.push(i);
	}
	for (int i = 0; i < n; i++)
		cout << ret[i] << " ";
	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/17298

• 문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

• 입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

• 출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

• 예제 입력

5 4
3 1
3 2
4 3
5 3

• 예제 출력

1 2

• 접근방식

인접 리스트를 기반으로 dfs 탐색, int형 dfs를 사용하여 반환

• 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <string.h>

using namespace std;

int n, m, a, b, mx;
int _save[10001], visited[10001];
vector<int> v[10001];



int dfs(int here)
{
	visited[here] = 1;
	int ret = 1;
	for (int there : v[here])
	{
		if (visited[there])
			continue;
		ret += dfs(there); // 결과값을 계속 모아서 반환
	}
	return ret;
}

int main()
{
	cin >> n >> m;

	while(m--)
	{
		cin >> a >> b;
		v[b].push_back(a); // 인접 리스트에 값 넣기
	}

	for (int i = 1; i <= n; i++)
	{
		memset(visited, 0, sizeof(visited));
		_save[i] = dfs(i); // i로 부터 몇개를 탐색할 수 있는지
		mx = max(_save[i], mx); // 가장 큰 값 구하기
	}

	for (int i = 1; i <= n; i++)
		if (mx == _save[i])
			cout << i << " ";
	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1325

• 문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

• 출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

• 예제 입력

13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

• 예제 출력

3
5

• 접근방식

dfs를 이용하여 치즈 녹이기, dfs로 치즈의 좌표를 알아낸 다음 테스트 케이스마다 녹여서 남아있는 치즈 갯수를 세고, 걸린 시간 증가, 무한 반복하다가 치즈가 전부 녹으면 빠져나오기

테스트 케이스마다 방문 기록 및 전 치즈의 좌표는 필요 없기 때문에 초기화후 dfs 시작

• 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <string.h>

using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

int n, m, hour, remain;
int _map[104][104], visited[104][104];
vector<pair<int, int>> v;



void dfs(int y, int x)
{
	visited[y][x] = 1;
	if (_map[y][x] == 1) // 치즈면 바로 종료
	{
		v.push_back({ y,x }); // 치즈의 좌표를 담음
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx])
			continue;
		dfs(ny, nx);
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> _map[i][j];
		}
	}

	while (1)
	{
		remain = 0;
		memset(visited, 0, sizeof(visited)); // 계속 초기화함
		v.clear(); // 남아 있는 치즈 벡터는 필요없으므로 계속 초기화함
		dfs(0, 0);

		for (pair<int, int> b : v) // 마지막으로 남아 있는 치즈 갯수 세고 녹이기
		{
			remain++;
			_map[b.first][b.second] = 0;
		}

		bool flag = 0; // 치즈가 전부 녹았나 안녹았나 체크

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (_map[i][j] != 0)
					flag = 1;
			}
		}

		hour++; // 시간을 체크

		if (!flag)
			break;
	}

	cout << hour << "\n" << remain;
	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2636

• 문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

• 출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

• 예제 입력

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

• 예제 출력

27

9

3

• 접근방식

벽을 3개 세운뒤 바이러스를 퍼트리고 안전 구역을 cnt해서 가장 높은 값을 구함

시간 복잡도를 따졌을 때 맵이 작아 벽을 3개 세우는 모든 경우의 수 가능, 벽을 3개 세우는 경우는 빈칸에 벽을 순서와 상관없이 넣는 경우 (64C3)

벽을 세운후 바이러스를 퍼트릴 때 dfs를 사용, 벽을 세울때마다 방문 구역 초기화, 벽을 세우고 안전구역 개수를 구하고 세운 벽 다시 초기화

• 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <string.h>

using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

int n, m,ret;
int _map[10][10], visited[10][10];
vector<pair<int, int>> virus_list;
vector<pair<int, int>> wall_list;


void dfs(int y, int x)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] || _map[ny][nx] == 1)
			continue;
		visited[ny][nx] = 1;
		dfs(ny, nx);
	}
}

int solve()
{
	memset(visited, 0, sizeof(visited)); // 함수를 사용 할때마다 방문 기록 초기화
	for (pair<int, int> b : virus_list)
	{
		visited[b.first][b.second] = 1; // 바이러스 리스트의 좌표값을 기반으로 dfs로 퍼트리기
		dfs(b.first, b.second);
	}

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (_map[i][j] == 0 && !visited[i][j]) // 안전 구역 구하기
				cnt++;
		}
	}

	return cnt;
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> _map[i][j];
			if (_map[i][j] == 2)
				virus_list.push_back({ i,j }); // 바이러스 좌표 저장
			if (_map[i][j] == 0)
				wall_list.push_back({ i,j }); // 벽 좌표 저장
		}
	}

	for (int i = 0; i < wall_list.size(); i++) // 3개를 순서 상관없이 뽑을때는 3중 for문으로 가능
	{
		for (int j = 0; j < i; j++)
		{
			for (int k = 0; k < j; k++)
			{
				_map[wall_list[i].first][wall_list[i].second] = 1; // 벽 3개를 세워보기
				_map[wall_list[j].first][wall_list[j].second] = 1;
				_map[wall_list[k].first][wall_list[k].second] = 1;
				ret = max(ret, solve());						   // 젤 높은 안전구역 숫자 구하기
				_map[wall_list[i].first][wall_list[i].second] = 0; // 벽 3개를 다시 초기화 시켜야함
				_map[wall_list[j].first][wall_list[j].second] = 0;
				_map[wall_list[k].first][wall_list[k].second] = 0;
			}
		}
	}
	cout << ret;
	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/14502

• 문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

• 입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.

• 출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

• 예제 입력

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

• 예제 출력

yes
yes
no
no
no
yes
yes

• 접근방식

짝짓기는 스택을 사용, 스택에 푸쉬하여 조건을 살펴 pop해주기, 마지막에 스택이 남아있거나 조건에 맞지 않으면 그대로  bool변수를 false로 만들고 break

• 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

bool check;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while (true)
	{
		string s;
		getline(cin, s);
		check = true;
		stack<char> stk;

		if (s == ".")
			break;

		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == '(') // 괄호 (면 그대로 푸쉬
				stk.push(s[i]);
			else if (s[i] == ')') // 괄호 )면
			{
				if (stk.size() && stk.top() == '[') // 스택이 있고 탑이 괄호 [면 break
				{
					check = false;
					break;
				}
				if (stk.size() && stk.top() == '(') // 스택이 있고 탑이 괄호 (면 그대로 pop
					stk.pop();
				else
					check = false;
			}
			if (s[i] == '[') // 괄호 [면 그대로 푸쉬
				stk.push(s[i]);
			else if (s[i] == ']') // 괄호 ] 면
			{
				if (stk.size() && stk.top() == '(') // 스택이 있고 탑이 괄호 (면 break
				{
					check = false;
					break;
				}

				if (stk.size() && stk.top() == '[') // 스택이 있고 탑이 괄호 [면 그대로 pop
					stk.pop();
				else
					check = false;
			}
		}

		if (check && stk.size() == 0)
			cout << "yes\n";
		else
			cout << "no\n";
	}

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/4949

• 문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

• 입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

• 출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

• 예제 입력

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

3
((
))
())(()

• 예제 출력

NO
NO
YES
NO
YES
NO

NO
NO
NO

• 접근방식

짝짓기는 스택을 사용, 짝이 되면(괄호가 완성이 되면) pop, 스택이 남아있으면 No, 스택이 남아있지 않으면 Yes 출력

• 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

int n;
string s;
bool check;

int main()
{
	cin >> n;


	for (int i = 0; i < n; i++)
	{
		cin >> s;
		stack<char> stk;
		check = 1;

		for (int j = 0; j < s.size(); j++)
		{
			if (s[j] == '(') // 괄호 (면 스택에 넣고
				stk.push(s[j]);
			else
			{
				if (stk.size()) // 아닌데(괄호 )고) 스택이 존재하면 pop
					stk.pop();
				else
					check = 0; // 스택이 존재하지 않으면 check = true
			}
		}

		if (stk.size())
			check = 0;
		if (check)
			cout << "YES\n";
		else
			cout << "NO\n";
	}

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/9012

• 문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

• 입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

• 출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

• 예제 입력

2

3

6

187

500

• 예제 출력

1666

2666

5666

66666

166699

• 접근방식

N의 범위를 보면 무식하게 풀어도 괜찮은 문제(경우의수 1000만 아래)

i를 666부터 시작해서 무한 반복하여 666을 찾으면 n--, n이 0이되면 종료, i를 출력

• 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int n;

int main()
{
	cin >> n;

	int i = 666;

	for (;; i++)
	{
		if (to_string(i).find("666") != string::npos) // npos = 찾는 문자열이 없는경우 반환
			n--;
		if (n == 0)
			break;
	}

	cout << i;

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1436