'알고리즘/백준' 카테고리의 글 목록 (2 Page)

1. 문제

1) 문제 링크

2631번: 줄세우기

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기

www.acmicpc.net

2) 설명

문제 자체는 이해하기 쉽다. 간단하게 말하면 N명의 아이들이 무작위로 서있는데 얘네를 순서에 맞게 줄세우게 만드는 최소 이동 횟수를 구하면 된다. 예를 들어 1 4 2 3 6 7 5 이렇게 서있으면 1 2 3 4 5 6 7로 세우면 된다. 하지만 나는 푸는 데 오래 걸렸다..

2. 풀이

1) 알고리즘

: DP

2) 풀이 설명

LCS를 사용하면 풀이는 간단하다. 왜냐하면 가장 많이 정렬되어 있는 집단을 고르고 나머지만 옮기는 게 가장 적게 아이들을 이동시키며 줄세울 수 있는 방법이기 때문이다.

위에 예에서 1 2 3 6 7 이 LCS가 된다. 그러면 4, 5만 제자리 찾아서 옮겨주면 되니까 최소 이동 횟수는 2가 된다.

사실 LCS는 얼마 전에도 풀고 여러번 했었는데, 머리가 나빠선지 응용 문제가 나오니까 LCS가 생각도 안 났다.

한 이틀 정도 헛다리만 집었지만 다행이도 스스로 LCS를 생각해서 풀 수 있었다.

솔직히 LCS를 풀어본 경험이 있다면 굉장히 쉬운 문제라고 생각하지만 나는 이틀을 고민해서 찾아낸 만큼 기분이 아주 좋았다.

3. 코드

/*
	줄 세우기
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	vector<int> children(N, 0), dp(N, 1);
	
	for(int i=0;i<N;i++)
		cin >> children[i];
	
	for(int i=0;i<N;i++)
		for(int j=i-1;j>=0;j--)
			if(children[i] > children[j])
				dp[i] = max(dp[i], dp[j] + 1);

	cout << N - *max_element(dp.begin(), dp.end()) << "\n";

	return 0;
}

4. 느낀점

1. 응용 문제를 자주 풀어보자!

'알고리즘 > 백준' 카테고리의 다른 글

[BOJ/14891] 톱니바퀴 (0)	2020.12.18
[백준/9656] 돌 게임 2 (0)	2020.11.02
[백준/9252] LCS 2 (0)	2020.10.27
[백준/11501] 주식 (0)	2020.10.18
[백준/15312] 이름 궁합 (1)	2020.10.18

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/9252

9252번: LCS 2

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

2) 설명

2. 풀이

1) 알고리즘

: DP

2) 풀이 설명

두 문자열이 주어질 때 가장 긴 공통 문자열의 길이와 그 문자열을 추출하는 문제.
ex) ABCDEG, BDAEFG 라면 BDEG가 가장 긴 공통 문자열이 되고 길이는 4가 된다.

첫 접근은 DP를 사용해서 공통 문자열의 길이를 구했다.
예를 들어 문자열 A, B가 주어지면 solve(A_idx, B_idx)를 재귀적으로 사용해서 가장 긴 문자열의 길이를 구하는 방식이다.
dp[x][y] 에는 A의 x번째 문자, B의 y번째 문자로부터 만들 수 있는 가장 긴 공통 문자열의 길이를 반환한다.
그러나 이 방식으로는 문자열의 길이는 구해도 어떤 문자열인지 추적하는 일이 너무 힘들었다.
그래서 검색 결과 다른 방식으로 DP를 사용하는 법을 배웠다.

일단 탑다운 방식보다는 바텀업 방식으로 진행해나갔다.

dp[i][j] 는 A의 i번째 문자까지와 B의 j-1번째 문자까지, B의 j번째 문자까지와 A의 i-1번째 문자까지 비교했을 때 가장 긴 공통 문자열의 길이를 의미한다.

그러므로 A[i-1] == B[j-1] 이라면 dp[i][j] = dp[i-1][j-1] + 1이 되고, 같지 않다면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])이 된다.

이부분이 상당히 이해하기 까다로웠다.

내가 이해한 바로는 (A[i], B[j-1])로 만들 수 있는 가장 긴 공통 문자열의 길이, (A[i-1], B[j])로 만들 수 있는 가장 긴 공통 문자열의 길이는 (A[i-1], B[j-1])로 만들 수 있는 가장 긴 공통 문자열의 길이와 같거나 1개 더 크기 때문으로 이해했다.

이렇게 다 돌고나면 dp[A의 길이][B의 길이]가 가장 긴 공통 문자열의 길이가 된다.

이후 만들어놓은 자취를 따라서 역추적해서 정답 문자열을 추출해내면 된다.

3. 코드

/*
	LCS 2
	DP
	Top-down
    길이만 구할 수 있었다..
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000

using namespace std;

string A = "", B = ""; 
vector<vector<int>> dp(MAX, vector<int>(MAX, -1));

int solve(int A_idx, int B_idx){
	if(A_idx == A.length() || B_idx == B.length())
		return 0;
	if(dp[A_idx][B_idx]>=0)
		return dp[A_idx][B_idx];
	for(int i=A_idx;i<A.length();i++){
		for(int j=B_idx;j<B.length();j++){
			if(A[i] == B[j]){
				dp[A_idx][B_idx] = max(dp[A_idx][B_idx], solve(i+1, j+1)+1);
			}
		}
	}
	return dp[A_idx][B_idx];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> A >> B;
	
	cout << solve(0, 0) << "\n";

	return 0;
}

/*
	LCS 2
	DP
	Bottom-up
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string A = "", B = ""; 
	cin >> A >> B;
	
	vector<vector<int>> dp(MAX, vector<int>(MAX, 0));

	//길이 구하기
	for(int i=1;i<=A.length();i++){
		for(int j=1;j<=B.length();j++){
			if(A[i-1] == B[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	cout << dp[A.length()][B.length()] << endl;
	
	//경로 찾아가기
	string answer = "";
	
	int x = A.length();
	int y = B.length();
	
	while(dp[x][y]>0){
		if(dp[x][y] == dp[x-1][y]){
			x--;
		} else if(dp[x][y] == dp[x][y-1]){
			y--;
		} else {
			answer = A[x-1] + answer;
			x--;
			y--;
		}
	}
	cout << answer << endl;
	return 0;
}

4. 느낀점

- 머리로는 대강 알겠는데 설명하는 게 너무 어렵다. 대강 이해한 게 문제인 것 같다.. 내 생각을 남들이 이해할 수 있도록 표현하는 연습을 하는 것도 중요하니까 어렵더라도 계속 설명하려 노력해야겠다.

- 단순히 길이만을 구하는 탑다운 풀이에서 벗어나오지를 못했다... 안 될 것 같으면 고집부리지 말고 다른 방식의 풀이도 생각해보자.

'알고리즘 > 백준' 카테고리의 다른 글

[백준/9656] 돌 게임 2 (0)	2020.11.02
[백준/2631] 줄세우기 (0)	2020.11.02
[백준/11501] 주식 (0)	2020.10.18
[백준/15312] 이름 궁합 (1)	2020.10.18
[백준/17070] 파이프 옮기기 1 (0)	2020.10.18

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/11501

11501번: 주식

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타

www.acmicpc.net

2) 설명

일별 주가가 주어졌을 때 주식을 사고 팔아 얻을 수 있는 최대의 이윤을 구하는 문제.

하루에 주식 하나 이하로만 살 수 있다.

2. 풀이

1) 알고리즘

: 단순 구현

2) 풀이 설명

주식을 매수한 시점보다 미래에 더 높은 가격에 매도할 수만 있으면 그 시점에는 무조건 주식을 매수해야 한다.(파는 건 여러 개 매도할 수 있기 때문)

그래서 해당 시점(i)에 주식을 매수했을 때 가능한 가장 높은 매도가를 기록해놓는 sellPrice 벡터를 사용했다.

그리고 sellPrice[i] - stock[i](매도가 - 매수가)가 양수일 때만 answer (답)에 더해주었다.

3. 코드

/*
	주식
	단순 구현
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;

	cin >> T;

	while(T--){
		long long N, answer = 0;
		cin >> N;
		vector<long long> stock(N);
		vector<long long> sellPrice(N, 0);

		for(int i=0;i<N;i++)
			cin >> stock[i];
		
		for(int i=N-2;i>=0;i--)
			sellPrice[i] = max(sellPrice[i+1], stock[i+1]);

		for(int i=0;i<N;i++)
			answer += max((sellPrice[i] - stock[i]), (long long)0);
		cout << answer << endl;
	}

	return 0;
}

4. 느낀점

- 처음에 별 생각 없이 sellPrice를 O(n^2)으로 구했다가 시간초과 났다.. 시간 많이 준다고 해도 (5초) 효율성 고려하자..

'알고리즘 > 백준' 카테고리의 다른 글

[백준/2631] 줄세우기 (0)	2020.11.02
[백준/9252] LCS 2 (0)	2020.10.27
[백준/15312] 이름 궁합 (1)	2020.10.18
[백준/17070] 파이프 옮기기 1 (0)	2020.10.18
[백준/5557] 1학년 (1)	2020.10.18

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/15312

15312번: 이름 궁합

영어 대문자 알파벳 26개의 획수는 순서대로 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 로 정한다. (출제자가 알파벳 대문자를 쓰는 방법이 기준이다)

www.acmicpc.net

2) 설명

그냥 영어 이름 궁합 보는 문제다.

여자친구랑 이름 궁합 봐보려고 풀어봤는데 궁합 정확도가 상당히 떨어지는 것 같다.

2. 풀이

1) 알고리즘

: 단순 구현

2) 풀이 설명

재귀를 사용해서 풀어보았다.

그냥 원소 두 개 남을 때까지 이웃 원소들의 합 벡터( (1,2), (2,3), (3,4), ... , (N-1,N)를 반환하는 함수를 계속 재귀 호출했다.

3. 코드

/*
	이름 궁합
	단순 구현
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solve(vector<int> nums){
	if(nums.size() == 2)
		return nums;
	vector<int> answer;
	for(int i=0;i<(int)nums.size()-1;i++)
		answer.push_back((nums[i]+nums[i+1])%10);

	return solve(answer);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	vector<int> cnt = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1};

	string jm, jh;
	cin >> jm >> jh;
	
	vector<int> nums;
	for(int i=0;i<jm.length();i++){
		nums.push_back(cnt[jm[i] - 'A']);
		nums.push_back(cnt[jh[i] - 'A']);
	}
	vector<int> result = solve(nums);
	for(auto r : result)
		cout << r;
	cout << endl;

	return 0;
}

4. 느낀점

- 재귀로 한번 풀어봤는데 비효율적이다.(시간적, 공간적 모두) 그렇지만 재미삼아 푼 문제라서 그냥 내비뒀다.

-> 반복문으로 두 개씩 줄여가도록 풀면 빨라진다.

'알고리즘 > 백준' 카테고리의 다른 글

[백준/9252] LCS 2 (0)	2020.10.27
[백준/11501] 주식 (0)	2020.10.18
[백준/17070] 파이프 옮기기 1 (0)	2020.10.18
[백준/5557] 1학년 (1)	2020.10.18
[백준/1261] 알고스팟 (0)	2020.10.16

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

2) 설명

길이 2의 파이프가 있다.

파이프는 가로, 세로, 대각선(좌상단 -> 우하단) 방향으로 밀 수 있다.

처음에 (1, 1), (1, 2)에 놓여진 파이프를 (N, M)까지 미는 경우의 수를 구하면 된다.

단 파이프는 오른쪽, 아래쪽, 대각선으로만 밀 수 있고, 직각으로는(가로 -> 세로, 세로->가로) 밀 수 없다.

또한 파이프의 이동 경로는 반드시 빈 칸이어야 하고, 대각선의 경우에는 파이프가 놓여져 있는 총 4칸이 빈 칸이어야 한다.

2. 풀이

1) 알고리즘

: DP

2) 풀이 설명

3차원 DP 벡터를 사용했다.

예를 들어 dp[x][y][z]는 x 방식(0 : 가로, 1 : 세로, 2 : 대각선)으로 (y, z)에 도달하는 경우의 수를 나타낸다.

2차원 DP를 사용하지 않고 이동 방식까지 나누어 3차 DP를 사용한 이유는 이동 방식(가로, 세로, 대각선)에 따라 다음에 이동할 수 있는 방식이 달라지기 때문이다.

모든 dp를 0으로 초기화해주고 가로 방식의 첫 행만 1로 초기화해주었다.

(i, j)로 이동하는 경우의 수는 다음과 같다.

1. (i, j-1)에서 가로 이동 (단 (i, j-1)에서는 세로로 도달했으면 안 된다.)

2. (i-1, j)에서 세로 이동 (단 (i-1, j)에서는 가로로 도달했으면 안 된다.)

3. (i-1, j-1)에서 대각선 이동

그러므로 점화식은 다음과 같이 세워진다.

dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1]

dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j]

dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] (단 좌하단, 우상단이 빈 공간일 때)

이렇게 다 돌고나면

dp[0][N][M] // 마지막에 가로 방식으로 (N, M)에 도달하는 경우의 수

+ dp[0][N][M] // 마지막에 세로 방식으로 (N, M)에 도달하는 경우의 수

+ dp[0][N][M] // 마지막에 대각선 방식으로 (N, M)에 도달하는 경우의 수

이 답이 된다.

3. 코드

/*
	파이프 옮기기 1
	알고리즘
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N, answer = 0;
	cin >> N;

	vector<vector<int>> house(N+1, vector<int>(N+1));
	/*
		0 - 가로
		1 - 세로
		2 - 대각선
	*/
	vector<vector<vector<int>>> dp(3,vector<vector<int>>(N+1, vector<int>(N+1, 0)));

	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			cin >> house[i][j];

	for(int i=2;i<=N && !house[1][i];i++)
		dp[0][1][i] = 1;

	for(int i=2;i<=N;i++){
		for(int j=2;j<=N;j++){
			if(!house[i][j]){
				dp[0][i][j] = dp[0][i][j-1] + dp[2][i][j-1];
				dp[1][i][j] = dp[1][i-1][j] + dp[2][i-1][j];
				if(!house[i-1][j] && !house[i][j-1]){
					dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1];
				}
			}
		}
	}
	for(int i=0;i<3;i++)
		answer += dp[i][N][N];
	
	cout << answer << endl;

	return 0;
}

4. 느낀점

- 초기에 (1, 1), (1, 2)에 파이프가 놓여져있다는 걸 모르고 가로, 세로, 대각선 다 출발했다가 틀렸다. 역시 문제를 잘 읽어야 한다.

'알고리즘 > 백준' 카테고리의 다른 글

[백준/11501] 주식 (0)	2020.10.18
[백준/15312] 이름 궁합 (1)	2020.10.18
[백준/5557] 1학년 (1)	2020.10.18
[백준/1261] 알고스팟 (0)	2020.10.16
[백준/9655] 돌 게임 (0)	2020.10.16

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/5557

5557번: 1학년

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀��

www.acmicpc.net

2) 설명

숫자 배열이 있으면 마지막 숫자 전에 = 기호를, 나머지 각 숫자 사이에 +나 - 기호를 넣어서 등식을 성립하게 만들 수 있는 경우의 수를 구하면 된다.

단 계산 과정 중(왼쪽부터 계산하는 방식) 음수나 20을 초과하는 수가 나와서는 안 된다.

2. 풀이

1) 알고리즘

: DP

2) 풀이 설명

0 ~ N-2 까지의 입력받은 숫자를 더하고 빼서 N-1번째에 입력받은 숫자를 만들어내면 된다.

즉 nums[0], nums[1], ... ,nums[N-2] 를 더하고 빼서 nums[N-1]을 만들면 된다.

그래서 i번째 이전 숫자들을 더하고 빼서 0부터 20까지 각각의 숫자를 만들 수 있는 경우의 수를 저장하는 DP 배열을 만들었다.

ex) DP[10][4] 에는 nums[0], nums[1], nums[2], nums[3], nums[4] 를 더하고 빼서 10을 만들 수 있는 경우의 수가 들어있다.

그러므로 DP배열은 21행( 0 ~ 20 ), N-1열( 0 ~ N-2 )을 가지게 된다.

초기값은 첫번째 DP[nums[0]][0] = 1로 주어진다.(첫 수(nums[0])으로 nums[0]을 만드는 경우의 수는 하나이기 때문에)

또한 점화식은 아래와 같이 세워진다.

DP[x][i] = DP[x][i] + DP[x-nums[i]] (단 x-nums[i] >= 0)

DP[x][i] = DP[x][i] + DP[x+nums[i]] (단 x+nums[i] <= 20)

이렇게 N-2열까지 돌리고나면 DP[nums[N-1]][N-2] 값이 답이 된다.(nums[0], nums[1], ... , nums[N-2]를 사용해서 nums[N-1]을 만드는 경우의 수)

3. 코드

/*
	1학년
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	const int maxSum = 20;
	int N;
	cin >> N;

	vector<int> nums(N);

	for(int i=0;i<N;i++)
		cin >> nums[i];

	vector<vector<long long>> DP(21, vector<long long>(N, 0));
	
	DP[nums[0]][0] = 1;

	for(int i=1;i<N-1;i++){
		for(int j=0;j<=maxSum;j++){
			if(j-nums[i] >= 0)
				DP[j][i] += DP[j-nums[i]][i-1];
			if(j+nums[i] <= maxSum)
				DP[j][i] += DP[j+nums[i]][i-1];
		}
	}

	cout << DP[nums[N-1]][N-2] << "\n";

	return 0;
}

4. 느낀점

- 값의 범위 잘 생각하기(long long 줘야하는데 int로 선언해서 틀렸었다.)

- 가독성 높은 점화식 세우기

'알고리즘 > 백준' 카테고리의 다른 글

[백준/15312] 이름 궁합 (1)	2020.10.18
[백준/17070] 파이프 옮기기 1 (0)	2020.10.18
[백준/1261] 알고스팟 (0)	2020.10.16
[백준/9655] 돌 게임 (0)	2020.10.16
[백준/7569] 토마토 (0)	2020.10.10

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/1261

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미

www.acmicpc.net

2) 설명

0(빈 공간), 1(벽)로 이루어진 미로가 있고 (1, 1)에서 (N, M)으로 도달하면서 1(벽)을 최소한으로 뚫고 갈 때, 뚫고 간 벽의 수를 구하는 문제.

2. 풀이

1) 알고리즘

: 우선순위 큐, BFS

2) 풀이 설명

처음에는 DFS를 사용하면 되겠다 생각했지만 BFS와 우선순위 큐를 사용하는 게 편하다고 생각했다.

일반적인 BFS문제를 풀듯이 풀었으나 큐 대신 우선순위 큐에 튜플( - 뚫은 벽의 수, x 좌표, y 좌표)를 넣어줬다.

우선순위 큐는 맥스 힙 방식(가장 큰 값부터 빼는 방식)으로 동작하기 때문에 뚫은 벽의 수를 음수처리 해줌으로써 가장 적게 벽을 뚫은 노드부터 빼오도록 했다.

ex) ㄱ : (-3, 2, 4)와 ㄴ : (-10, 3, 5)가 있으면 ㄱ은 벽을 3번, ㄴ은 벽을 10번 뚫은 것이고, 우선순위 큐에서는 -3 > -10 이기 때문에 ㄱ을 먼저 뽑는다.

즉 해당 노드를 처음 방문한다면 그 방문은 벽을 최소로 뚫는 경로로 방문한 것이 된다.

그러므로 BFS를 돌던 중 (N, M) 좌표를 방문한다면 바로 while문을 탈출하고 답을 내면 된다.

3. 코드

/*
	알고스팟
    BFS, Priority queue
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, -1, 1};

	int N, M, answer = -1;
	cin >> M >> N;
	
	vector<vector<char>> miro(N+1, vector<char>(M+1));
	vector<vector<bool>> visited(N+1, vector<bool>(M+1, false));

	priority_queue<tuple<int, int, int>> pq;

	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			cin >> miro[i][j];

	pq.push({0, 1, 1});
	visited[1][1] = true;

	while(!pq.empty()){
		int wall = get<0>(pq.top());
		int x = get<1>(pq.top());
		int y = get<2>(pq.top());
		pq.pop();
		
		if(x==N && y==M){
			answer = -wall;
			break;
		}
		for(int i=0;i<4;i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx<=0 || nx>N || ny<=0 || ny>M)
				continue;
			if(visited[nx][ny])
				continue;
			
			visited[nx][ny] = true;
			pq.push({(miro[nx][ny]=='1'? wall-1 : wall), nx, ny});
		}
	}
	
	cout << answer << endl;

	return 0;
}

4. 느낀점

- 입력이 M, N 순서로 주어져서 일반적으로 생각하는 방식(N -> M)이랑 달라서 헷갈렸다.

- visited를 안 써도 되지 않을까 잠시 생각했다. -> 무한루프 돌 수도 있다.

- 인풋 한 줄을 한 글자씩 받아야 하는 걸 그냥 int로 받아버렸다. 입력 받기 신경쓰자.

- 아직 tuple 사용법이 많이 미숙하다. 연습하자.

'알고리즘 > 백준' 카테고리의 다른 글

[백준/17070] 파이프 옮기기 1 (0)	2020.10.18
[백준/5557] 1학년 (1)	2020.10.18
[백준/9655] 돌 게임 (0)	2020.10.16
[백준/7569] 토마토 (0)	2020.10.10
[백준/2606] 바이러스 (0)	2020.10.10

1. 문제

1) 문제 링크

: www.acmicpc.net/problem/9655

9655번: 돌 게임

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

www.acmicpc.net

2) 설명

상근이와 창영이가 N개의 돌을 차례로 1개 혹은 3개씩 가져가면서 마지막 돌을 가져가는 사람이 이기는 게임을 한다.

상근이가 선공이고 둘 다 최선을 다할 때 누가 이기는지 출력하는 문제.(상근 SK, 창영 CY)

2. 풀이

1) 알고리즘

: DP

2) 풀이 설명

간단한 DP 문제.

N번째 돌을 반드시 집기 위해선 N-2번째 돌을 가져가면 된다.

내가 N-2번째 돌을 집으면 돌은 두 개가 남고 상대방은 1개, 3개의 돌만 가져갈 수 있기 때문에, 즉 남은 두 개 중 1개만 가져갈 수밖에 없기 때문에 상대가 돌 1개를 가져가고 마지막 N번째 돌을 가져오면 된다.

그러므로 초기값 A1 = 상근이가 이기는 경우, A2 = 창영이가 이기는 경우로 두고 N번까지 A_N = A_(N-2)을 돌리면 된다.

나는 bool 타입으로 dp값을 저장했다. 상근이가 이기는 경우 = true, 창영이가 이기는 경우 = false

3. 코드

/*
	돌 게임
	DP
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;
	
	vector<bool> dp(N+1);

	dp[1] = true;
	dp[2] = false;

	for(int i=3;i<=N;i++)
		dp[i] = dp[i-2];
		 
	cout << (dp[N]? "SK\n" : "CY\n");

	return 0;
}

4. 느낀점

- 1차원 dp(점화식) 감잡기 좋은 문제라고 생각한다.

'알고리즘 > 백준' 카테고리의 다른 글

[백준/17070] 파이프 옮기기 1 (0)	2020.10.18
[백준/5557] 1학년 (1)	2020.10.18
[백준/1261] 알고스팟 (0)	2020.10.16
[백준/7569] 토마토 (0)	2020.10.10
[백준/2606] 바이러스 (0)	2020.10.10