아주정은's 릴상

내가 어떻게 풀었는지 기록할려고 쓴다.

​문제는 문자열을 받았을때, 문자열을 숫자로 변환하는게 문제다.

그럼 일단 문자열을 입력 받는게 우선이다.

문자열을 입력받고, 문자열을 반복문을 통해 하나하나 읽어 나간다.

경우의 수는 네가지이다. (,),[,] 이렇게 네가지로 나누어서 처리를 해준다.

근데 나는 처음에 ),] 이 닫아주는 문자열이 나올때 숫자를 업데이트 할려고했다.

예를 들면, (()[[]]) = 2*(2+3*(3)) = 22 이다. 그런데 분배법칙으로 풀면 2*2 + 2*3*3 이렇게 나온다.

내 생각이 짧았다. 분배법칙이 가능하기때문에 tmp 변수를 초기에 1로 두고, 괄호를 열어주는 문자가 나오면 곱해주면서 분배법칙이 잘적용될수있는 파라미터를 만든다. 그러다가 닫아주는 문자가 나오면 tmp를 결과값에 더해주고 나눠준다.

그리고 나머지 에러들을 처리해준다. 만약 잘못된물자열이라면 짝이 안맞을 것이다. 스택에서 나오는게 현재 문자와 짝이 안맞을 경우, 문자열이 끝나지 않았는데 스택이 비어버리는 경우, 문자열이 끝났는데 스택에 남아있는 경우가 있을것이다.

솔직히 이해는 되지만 말로 설명하기는 좀 힘들다.

​알고리즘 문제는 많이 풀어보면서 외우는것도 좋은 방법인것같다.

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

using namespace std;


int main()
{
	int tmp = 1, output = 0;
	string str;
	bool wrong = false;
	stack<char> st;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			st.push('(');
			tmp *= 2;
		}
		else if (str[i] == '[') {
			st.push('[');
			tmp *= 3;
		}

		else if (str[i] == ')') {
			if (st.empty()) {
				wrong = true;
				break;
			}
			if (st.top() == '(') {
				if (str[i - 1] == '(') output += tmp;
				st.pop();
				tmp /= 2;
			}
			else {
				wrong = true;
				break;
			}
		}
		else if (str[i] == ']') {
			if (st.empty()) {
				wrong = true;
				break;
			}
			if (st.top() == '[') {
				if(str[i-1]=='[') output += tmp;
				st.pop();
				tmp /= 3;
			}
			else {
				wrong = true;
				break;
			}
		}
	}

	if (wrong or !st.empty()) {
		cout << 0 << endl;
	}
	else {
		cout << output << endl;
	}
}
​

문제는 굉장히 쉬웠는데, 흠....초기화를 간과했다.

​문제 쉽다고 너무 자만고릴라였다 이거야~

방문했다는 표시 배열을 항상 초기화를 잘해주자.

이것은 그냥 bfs이용해서 풀면 아주쉽다.

​

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
	int z;
	int time;
};

char board[32][32][32];
bool vis[32][32][32];

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


int main()
{
	
	while (1) {
		int L, R, C;
		string str;
		queue<Que> Q;
		cin >> L >> R >> C;

		if (L == 0 or R == 0 or C == 0)break;

		for (int i = 0; i < L; i++) {
			for (int j = 0; j < R; j++) {
				cin >> str;
				for (int k = 0; k < C; k++) {
					board[i][j][k] = str[k];
					if (board[i][j][k] == 'S') {
						Q.push({ i,j,k,0 });
						vis[i][j][k] = true;
					}
				}
			}
		}

		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();
			for (int i = 0; i < 6; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				int nz = cur.z + dz[i];
				if (nx<0 or nx>L - 1 or ny<0 or ny>R - 1 or nz<0 or nz>C - 1)continue;
				if (board[nx][ny][nz] == 'E') {
					cout << "Escaped in " << cur.time + 1 << " minute(s)." << endl;
					goto ijsilver;
				}
				if (board[nx][ny][nz] == '.' and vis[nx][ny][nz] == false) {
					Q.push({ nx,ny,nz,cur.time + 1 });
					vis[nx][ny][nz] = true;
				}
			}
		}

		cout << "Trapped!" << endl;

	ijsilver:
		;

		for (int i = 0; i < L; i++) {
			for (int j = 0; j < R; j++) {
				for (int k = 0; k < C; k++) {
				
					vis[i][j][k] = false;
				}
			}
		}
	}
	
}

이건 문제가 엄청 어려운건 아닌것같은데, 생각을 많이 하지 않아서 좀 해맸다.

오지게 틀렸다....

​후기를 쓰자면, 처음에는 BFS로 큐를 사용해서 풀려고했다. 근데 가장 작은 시간을 출력해야하기 때문에 적절하지 않았다.

​그래서 우선순위 큐를 사용할려고하였다. 근데 우선순위큐를 사용할경우 반례들이 발생한다.

​흠....그래서 구글에 백준 13549번 c++ 이라는 키워드를 검색하고 여러가지 정답코드를 봤는데,

​데큐를 이용하는게 나쁜생각같지는 않아서 데큐로 골랐다. 실은 나는 평소 The Q를 좋아하기 때문에 선택한 경향도 없지않아 있다.

​음 일단, 곱하기 2를 할경우에는 앞으로 푸쉬하고, 더하기 빼기를 할때는 뒤로 푸시를 한다.

​생각해보자. 5에서 17을 찾아갈때, 타임이 0000011111 이런식으로 있을때, 앞에서만 pop을 하면 앞에는

타임이 가장 작은것들만 들어가고 자연스럽게 뒤로 타임이 높은게 들어간다.

​그래서 데큐를 사용하면 괜찮다.

​구현은 코드가 짧기때문에 설명은 생략한다.

#include <iostream>
#include<deque>
#include<string>

using namespace std;

struct Que {
	int x;
	int time;
};

bool vis[100001];



int main()
{
	int a, b;
	cin >> a >> b;
	deque<Que> Q;
	Q.push_front({ a,0 });
	vis[a] = true;

	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop_front();

		if (cur.x == b) {
			cout << cur.time << endl;
			break;
		}

		if (cur.x * 2 < 100001 and vis[cur.x * 2] == false) {
			Q.push_front({ cur.x * 2,cur.time });
			vis[cur.x * 2] = true;
		}
		if (cur.x + 1 < 100001 and vis[cur.x + 1] == false) {
			Q.push_back({ cur.x + 1,cur.time + 1 });
			vis[cur.x + 1] = true;
		}
		if (cur.x - 1 >= 0 and vis[cur.x - 1] == false) {
			Q.push_back({ cur.x - 1,cur.time + 1 });
			vis[cur.x - 1] = true;
		}
	}

}

문제가 다른 숨바꼭질과 굉장히 비슷하다. 그래서 금방 최소값은 구할수있었는데, 경로를 어떻게 찾을까 생각을 해보았다.

​트리를 그리면 굉장히 쉬운거지만 어떻게 구현을 해야할지 고민을 했다.

음 그냥 무식하게 해보면, 문자 배열을 선언하고, 진행될때마다 어떤 수식을 썻는지 저장을 해준다.

그다음 역추적 방식으로 찾아가주면 된다.

굉장히 코드가 무식하지만, 그래도 원샷원킬했음^^

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int time;
};

bool vis[100001];
char mul[100001];
int arr[100001];

//굉장히 무식한 방법같지만 순간 떠오른게 이거여서 해봤다...

int main()
{
	int a, b,i,j,temp;
	cin >> a >> b;
	queue<Que> Q;
	Q.push({ a,0 });
	arr[0] = a;
	vis[a] = true;
	mul[a] = '=';

	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();

		if (cur.x == b) {
			cout << cur.time << endl;
			i = cur.x;
			j = cur.time;
			break;
		}

		if (cur.x * 2 < 100001 and vis[cur.x * 2] == false) {
			Q.push({ cur.x * 2,cur.time+1 });
			vis[cur.x * 2] = true;
			mul[cur.x * 2] = '/';
		}
		if (cur.x + 1 < 100001 and vis[cur.x + 1] == false) {
			Q.push({ cur.x + 1,cur.time + 1 });
			vis[cur.x + 1] = true;
			mul[cur.x + 1] = '-';
		}
		if (cur.x - 1 >= 0 and vis[cur.x - 1] == false) {
			Q.push({ cur.x - 1,cur.time + 1 });
			vis[cur.x - 1] = true;
			mul[cur.x - 1] = '+';
		}
	}
	temp = j;
	while (mul[i] != '=') {//등호가 나올때까지 출력해준다. 곱하기를 했을경우 i를 나누면 그전 숫자가 됨
		if (mul[i] == '/') {
			arr[j] = i;
			i = i / 2;
		}
		else if (mul[i] == '-') {
			arr[j] = i;
			i = i - 1;
		}
		else if (mul[i] == '+') {
			arr[j] = i;
			i = i + 1;
		}
		j--;
	}
	for (int k = 0; k < temp + 1; k++) {//출력해준다.
		cout << arr[k] << " ";
	}
}

음....벽부수고 이동하기랑 굉장히 비슷한 문제이다.

​처음에는 편하게 bfs이용해서 해봤는데 반례들이 많이 적용되었다.

처음에는 갱신형으로 풀어봣는데 반례들이 많이 발견되서 포기하고,

벽부수고 이동하기처럼 문제를 풀었다.

그리고 메모리초과가 계속 나와서 어떤 조건문이 잘못되었나 계속 찾아봤지만,

어이없게도 vis[nx][ny]=true; 이렇게 해야하는데 ==으로 쓰는바람에 메모리 초과가

계속 나타났다. 앞으로는 조심하자.

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
	int wcnt;
	int time;
};

int board[202][202];
bool vis[202][202][31];
int dx[4] = { 1,0,-1,0 };
int dy[4] = {0, 1, 0, -1};
int hx[8] = { 2,2,1,1,-1,-1,-2,-2 };
int hy[8] = { 1,-1,2,-2,2,-2,1,-1 };

int main()
{
	int k, w, h;
	cin >> k;
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> board[i][j];
		}
	}
	queue<Que> Q;
	Q.push({ 0,0,0,0 });
	vis[0][0][0] = true;
	bool success = false;
	
	while (!Q.empty()) {

		auto cur = Q.front();
		Q.pop();
		if (cur.x == h - 1 and cur.y == w - 1) {
			cout << cur.time << endl;
			success = true;
			break;
		}

		if (cur.wcnt < k) {
			for (int i = 0; i < 8; i++) {
				int nx = cur.x + hx[i];
				int ny = cur.y + hy[i];

				if (nx<0 or nx>h - 1 or ny<0 or ny>w - 1)continue;
				if (board[nx][ny] == 0 and vis[nx][ny][cur.wcnt + 1] == false) {
					Q.push({ nx,ny,cur.wcnt + 1,cur.time + 1 });
					vis[nx][ny][cur.wcnt + 1] = true;
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];

			if (nx<0 or nx>h - 1 or ny<0 or ny>w - 1)continue;
			if (board[nx][ny] == 0 and vis[nx][ny][cur.wcnt] == false) {
				Q.push({ nx,ny,cur.wcnt,cur.time + 1 });
				vis[nx][ny][cur.wcnt] = true;
			}
		}
	}
	if (!success) {
		cout << -1 << endl;
	}
}

숨바꼭질 지긋지긋.....

​음 이문제는 4일?정도 생각을 해본것같다.

이문제에 대한 풀이가 많이 않아서 고민을 많이 해야했던것같다.

일단 풀이 방법의 요점은 언니가 짝수초에 방문한 위치는 짝수초에 또 방문할수있다는것이다.

홀수초도 마찬가지이다. 언니가 16이라는 위치에 짝수초에 방문했다면, 다음 +1, -1을 통해서 다음짝수초에도 방문 할 수 있게된다.

어떤풀이는 언니가 방문한 모든 위치를 배열에 저장하는 방식을 하셨다. 그 방법을 써볼려고 하니깐 음...그럼 언니의 위치가 0보다 작아지거나 500000보다 높아져야 끝이나기 때문에 포기하고 다시 내 생각으로 돌아왔다.

먼저, 나는 시간에 따라 동생의 위치를 파악한다.

그리고 현재 큐에는 현재 초까지 언니가 방문한 위치들이 들어있다. 그니깐 나는 초별로 언니가 동생을 잡을수있는지 검사하는 것이다. 그래서 현재 초에 큐에서 나온것이 동생의 위치랑 같거나, 동생의 위치가 방문을 했던것이면, 현재 초를 출력해주는 것이다.

이게 말만으로는 되게 쉬웠는데, 생각하고 직접 행동에 옮기기에는 오래걸렸다.

다른 풀이보다 나름 코드가 깔끔하다고 생각하니 다른사람들도 참고하면 좋겠다^^

그럼 바위^^

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int time;
};

bool vis[500001][2];

int sum(int n) {
	return n * (n + 1) / 2;
}


int main()
{
	int N, K;//언니 위치 : N, 동생위치 : K
	cin >> N >> K;
	
	queue<Que> Q;
	Q.push({ N,0 });
	vis[N][0] = true;
	
	int answer = -1, i = 0;
	int nk;

	while (1) {
		int size = Q.size();
		nk = K + sum(i);
		//cout << "nk=" << nk<<endl;
		if (nk < 0 or nk>500000) {
			break;
		}
		while (size--) {
			auto cur = Q.front();
			//cout << "cur.x=" <<cur.x << endl;
			Q.pop();
			if (cur.x == nk or vis[nk][i%2]==true) {
				answer = i;
				goto ijsilver;
			}
			if (cur.x - 1 >= 0 and vis[cur.x - 1][(cur.time + 1) % 2] == false) {
				Q.push({ cur.x - 1,cur.time + 1 });
				vis[cur.x - 1][(cur.time + 1) % 2]=true;
			}
			if (cur.x + 1 <= 500000 and vis[cur.x + 1][(cur.time + 1) % 2] == false) {
				Q.push({ cur.x + 1,cur.time + 1 });
				vis[cur.x + 1][(cur.time + 1) % 2]=true;
			}
			if (cur.x *2 <= 500000 and vis[cur.x *2][(cur.time + 1) % 2] == false) {
				Q.push({ cur.x*2,cur.time + 1 });
				vis[cur.x*2][(cur.time + 1) % 2]=true;
			}
		}
		i++;

	}
ijsilver:
	cout << answer << endl;

}

항상 별찍기 문제는 어려운것같다.

이 문제는 별을 찍는 패턴을 보면 3일때 찍는 것들이 연속적으로 있고, 꼭 3개씩 반복된다.

이런 문제는 재귀의 전형적인 문제라고 볼수있다. 그런데 패턴을 찾아내기가 여간 쉽지않았다.

그리고 처음부터 출력을 할려고 하니 막막했는데, 배열을 써서 배열에 넣을 생각으로 하니깐 할만 했던것같다.

소스코드는 제법 간단하다. n=3일때, 파라미터로 들어온 좌표를 갖고 배열의 값을 변경해준다.

그리고 파라미터들을 조합해서, 좌표들을 조정해서 다시 함수를 호출하는 방식이다.

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 10000;
bool board[MAX][MAX];

void input_star(int n, int x, int y) {
	if (n == 3) {
		board[x][y] = true;
		board[x + 1][y - 1] = true;
		board[x + 1][y + 1] = true;
		for (int i = 0; i < 5; i++) {
			board[x + 2][y - i + 2] = true;
		}
		return;
	}

	input_star(n / 2, x, y);
	input_star(n / 2, x + n / 2, y - n/2 );
	input_star(n / 2, x + n / 2, y+n/2);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int input;
	cin >> input;

	for (int i = 0; i < input; i++) {
		for (int j = 0; j < 2 * input - 1; j++) {
			board[i][j] = false;
		}
	}
	input_star(input,0,input-1);
	
	for (int i = 0; i < input; i++) {
		for (int j = 0; j < 2*input-1; j++) {
			if (board[i][j]) cout << "*";
			else cout << " ";
		}
		cout << endl;
	}
}

이 문제는 처음에 다른 BFS문제와 비슷하게 풀이를 생각하였다.

L과 L사이에 길이 있는지 없는지 판단한다.

길이 없을 경우 얼음을 녹이고, 다시 길을 있는지 판단한다.

백조 두마리는 항상 존재하고 얼음이 녹으면 길이 존재하기에 반복문을 통해서 길을 찾을때까지 반복하면 답은 나온다.

문제는 시간초과이다.

처음에는 무식하게 BFS로 L부터 L까지의 길을 찾으려고 했다. 그랬더니 시간초과가 떴지모얌...

생각을 해볼려다가....솔직하게 구글에 백준 3197번 검색^^

꾸준함님꺼 참고해서 풀었다. 여러가지 방법이 있지만, 내가 아는 방법을 설명해보겠다.

시간초과가 나는 이유는 L부터 L까지 갈려고할때 BFS로 계속 하면 시간초과가 발생한다. 1500x1500이기 때문이다.

솔직히 시간복잡도 계산은 잘못한다. 그래서 처음에 둘중에 하나의 L이 주변에 있는 물을 싹 둘러본다. BFS로.

그러면 거기에 L이 없다고 판단되면 물옆에 얼음은 시간이 지나면 녹겠지? 그것을 nextQ에 넣는다.

그리고 얼음들을 녹여준다.

그니깐 nextQ에는 L이 다음에 둘러볼 물만 남는것이다. 가릿? 전에 물은 방문했으니깐 안가도된다~ 이말이야

이게 키포인트이다.

그리고 얼음 녹이는 것도, 나는 for문 두개써서 다 돌면서 빙산인데 옆에 물이면 녹인다. 이렇게 판단했었다.

근데 지금은 waterQ라는 것을 생성해서 처음에 물인 곳을 다 때려박고, 그 다음 옆에 얼음인것을 녹여주는 방식을 선택했다.

아무쪼록 주옥같아서 여러번 풀어봐야할 문제이다.

#include <iostream>
#include<queue>
#include<string>

using namespace std;

struct Que {
	int x;
	int y;
};

char board[1501][1501];
bool vis[1501][1501];

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

int main()
{
	int R, C;
	int lx, ly;
	string str;
	int time = 0;

	queue<Que> waterQ;
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		cin >> str;
		for (int j = 0; j < C; j++) {
			board[i][j] = str[j];
			if (board[i][j] == 'L') {
				lx = i;
				ly = j;//L위치
			}//나중에 입력된 L의 위치가 저장된다.
			if (board[i][j] == '.' or board[i][j] == 'L') {
				waterQ.push({ i,j });
			}
		}
	}

	queue<Que> Q;
	Q.push({ lx,ly });
	vis[lx][ly] = true;

	while (1) {
		queue<Que> nextQ;
		bool suc = false;
		while (!Q.empty() and !suc) {
			auto cur = Q.front();
			Q.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx<0 or nx>R - 1 or ny<0 or ny>C - 1)continue;
				
				if (board[nx][ny] == 'L' and vis[nx][ny] == false) {
					suc = true;
					break;
				}//다른백조 만나면 성공
				if (board[nx][ny] == '.' and vis[nx][ny] == false) {
					Q.push({ nx,ny });
					vis[nx][ny] = true;
				}//물인데 방문한적없으면 큐에 넣는다.
				if (board[nx][ny] == 'X' and vis[nx][ny] == false) {
					nextQ.push({ nx,ny });
					vis[nx][ny] = true;
				}//물옆에 있는 얼음이면 다음에 방문할것이다.
			}
		}
		if (suc) {
			cout << time << endl;
			break;
		}
		Q = nextQ;

		int watersize = waterQ.size();

		while (watersize--) {
			auto cur = waterQ.front();
			waterQ.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (nx<0 or nx>R - 1 or ny<0 or ny>C - 1)continue;
				if (board[nx][ny] == 'X') {
					waterQ.push({ nx,ny });
					board[nx][ny] = '.';
				}
			}
		}
		time++;

	}
}

이 문제는 런타임에러, 메모리초과, 컴파일에러가 정말 많이 발생했다.

비주얼 스튜디오에서는 돌아가는데 백준서버에서는 돌아가지 않았다.

처음에 어느 지점에서 다른 지점의 불을 켤 수 있는 숫자를 받을때, 이것을 어떻게 저장해야할까 고민을 많이 했다.

그래서 3차원 배열을 사용하기로 하였다. 근데 문제는 숫자가 2만개까지 가능하기에 배열 크기가 너무 커져서

런타임 에러가 발생했다. 그래서 구글링.....

구글링을 해보니 다른사람은 vector를 썻더라.... 벡터는 좋다고는 들었지만, 안보에 있어서 나는 보수이기 때문에..... 쉽게 받아들이고 싶지 않았다. 하지만 계속되는 메모리초과와 런타임에러로 나는 벡터를 수용했다.

서론은 여기까지고, 이문제는 1,1은 항상 불이 켜져있다. 그래서 1,1에서 켤수있는 불들을 일단 켜준다.

그다음 상하좌우를 살피고 갈수있는곳을 간다. 그리고 거기서 새로운 불을 켠다면, 다시 1,1부터 BFS를 통해 배열을 돈다.

음 BFS를 여러번하는거는 시간이 그렇게 많이 들지는 않나보다?라는 생각을 했다.

암튼 교훈은 vector 사용하자. 여러 함수 알아놓자. 입니다.

신문물 받아들입시다!

#include <iostream>
#include<queue>
#include<cstring>
#include<vector>

using namespace std;

struct Que {
	int x;
	int y;
};

//Que board[101][101][20001];

vector<Que> board[101][101];
bool light[101][101];
bool vis[101][101];

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

int main()
{
	int N, M;
	int a, b, c, d;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c >> d;
		board[a - 1][b - 1].push_back({c-1,d-1});
	}

	while (1) {
		memset(vis, false, sizeof(vis));//cstring헤터 필요 vis를 초기화
		queue<Que> Q;
		Q.push({ 0,0 });//(0,0)부터 시작하기 때문에
		vis[0][0] = true;
		light[0][0] = true;//불 계속켜주는건 비효율이지만 어쩔수없음
		bool flag = false;
		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();
			if (!board[cur.x][cur.y].empty()) {
				for (int i = 0; i < board[cur.x][cur.y].size(); i++) {
					auto c = board[cur.x][cur.y][i];
					light[c.x][c.y] = true;
				}//불을 켜준다.
				board[cur.x][cur.y].clear();//불을 켜준뒤 벡터에 남아있는거 없앤다.
				flag = true;//새로운방에 불을 켰다는 의미
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx<0 or nx>N - 1 or ny<0 or ny>N - 1)continue;
				if (light[nx][ny] == true and vis[nx][ny] == false) {
					Q.push({ nx,ny });
					vis[nx][ny] = true;
				}
			}//상하좌우 돌면서 불켜진방 탐색
		}
		if (!flag) {
			break;
		}//새롭게 불켜진방이없으면 break
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (light[i][j])cnt++;
		}
	}//불켜진방 갯수 세보자.
	cout << cnt << endl;
}

정확히 어떻게 되는지는 모르겠고, 외워야겠다.

아래처럼하면 start에대한 내림차순으로 되다가 start가 같으면 value에 대한 내림차순으로 진행한다.

부등호 반대로 바꾸면 반대로 된다. 참고하자.

struct a {
	int start;
	int value;
};

struct cmp {
	bool operator()(a t, a u) {
		if (t.start == u.start) {
			return t.value < u.value;//value에 대해 내림차순임
		}
		else {
			return t.start > u.start;
		}
	}
};

priority_queue<a, vector<a>, cmp> pq;