Mist16's Dev Blog

문제

• 9465번 : 스티커
• Rank : Silver I
• https://www.acmicpc.net/problem/9465

풀이 전략

• i번째 줄의 스티커를 뗄 때, 경우의 수는 다음과 같이 나타낼 수 있다
  • i-1번째 줄에서 스티커를 떼지 않음
  • i-1번째 줄에서 위쪽 줄 스티커를 뗌
  • i-1번째 줄에서 위쪽 줄 스티커를 떼지 않음.
• 그리고, i-1번쨰 줄에서 다음 상태였을때, i번째 줄의 각 상태로 이행할 수 있다.
  • i-1번째 줄에서 떼지 않음/위쪽을 뗌 -> 아래쪽을 뗄 수 있음
  • i-1번째 줄에서 뗴지 않음/아래쪽을 뗌 -> 위쪽을 뗄 수 있음
  • 모든 경우의 수 -> 떼지 않음
    • 하지만 i-1번째 줄에서 떼지 않은 경우의 스코어 < i-1번째 줄에서 위쪽/아래쪽을 뗀 경우의 스코어이기 때문에, 위쪽/아래쪽을 뗀 경우만만을 비교한다
• for루프를 사용하여 1~N번째 줄까지, 3가지 상태에 대하여 도출가능한 이전 상태 중 높은 값을 선택하는 식으로 계산을 이어나간다.

// 0 : 위쪽을 뗌
// 1 : 아래쪽을 뗌
// 2 : 떼지 않음
unsigned int stickerMap[100000][2];
unsigned int maxPoint[100000][3];

	for (int i = 1; i < N; i++)
	{
		//up
		if (maxPoint[i-1][1] > maxPoint[i-1][2])
		{
			maxPoint[i][0] = maxPoint[i - 1][1] + stickerMap[i][0];
		}
		else
			maxPoint[i][0] = maxPoint[i - 1][2] + stickerMap[i][0];
		//down
		if (maxPoint[i - 1][0] > maxPoint[i - 1][2])
		{
			maxPoint[i][1] = maxPoint[i - 1][0] + stickerMap[i][1];
		}
		else
			maxPoint[i][1] = maxPoint[i - 1][2] + stickerMap[i][1];
		//none
		if (maxPoint[i - 1][0] > maxPoint[i - 1][1])
			maxPoint[i][2] = maxPoint[i - 1][0];
		else
			maxPoint[i][2] = maxPoint[i - 1][1];
	}

• 계산이 끝난 후, maxPoint[N-1]의 0~2번째 값 중 큰 값을 리턴한다.

전체 소스 코드

#include <iostream>
#include <memory.h>
using namespace std;

unsigned int stickerMap[100000][2];
unsigned int maxPoint[100000][3];

int testCases = 0;
int N = 0;

void run()
{
	maxPoint[0][0] = stickerMap[0][0];
	maxPoint[0][1] = stickerMap[0][1];
	maxPoint[0][2] = 0;

	for (int i = 1; i < N; i++)
	{
		//up
		if (maxPoint[i-1][1] > maxPoint[i-1][2])
		{
			maxPoint[i][0] = maxPoint[i - 1][1] + stickerMap[i][0];
		}
		else
			maxPoint[i][0] = maxPoint[i - 1][2] + stickerMap[i][0];
		//down
		if (maxPoint[i - 1][0] > maxPoint[i - 1][2])
		{
			maxPoint[i][1] = maxPoint[i - 1][0] + stickerMap[i][1];
		}
		else
			maxPoint[i][1] = maxPoint[i - 1][2] + stickerMap[i][1];
		//none
		if (maxPoint[i - 1][0] > maxPoint[i - 1][1])
			maxPoint[i][2] = maxPoint[i - 1][0];
		else
			maxPoint[i][2] = maxPoint[i - 1][1];
	}

}

int main()
{
	int numb, temp;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> testCases;

	for (int i = 0; i < testCases; i++)
	{
		unsigned int tempMaxValue = 0;
		//input
		cin >> N;
		for (int j = 0; j < N; j++)
		{
			cin >> stickerMap[j][0];
		}
		for (int j = 0; j < N; j++)
		{
			cin >> stickerMap[j][1];
		}
		//run
		run();

		for(int j = 0; j < 3; j++)
		{
			if (tempMaxValue < maxPoint[N-1][j])
				tempMaxValue = maxPoint[N-1][j];
		}
		cout << tempMaxValue << "\n";
	}
	return 0;
}

Note

• 이전 계산값을 사용하지 않기때문에, maxPoint를 배열 대신 변수 6개(current, next)로 사용하는 방법도 생각할만했다. 다만 그 경우 계산량이 부족하여, 문제의 메모리 제한(256MB)을 최대한 활용하는 방향으로 풀이했다.
• 입력을 받아오는 양이 많기때문에, sync_with_studio, cin.tie(NULL)을 사용하여 입력을 최적화해주지 않으면 시간제한에 걸린다.

문제

• 11053번 : 가장 긴 증가하는 부분 수열
• Rank : Silver II
• 링크 : https://www.acmicpc.net/problem/11053

풀이 전략

• for문을 사용하여, 현재 인덱스 앞에서 자기보다 큰, 방문할 수 있는 위치를 확인하여 진행한다.
  • 20 20 50 10 70 -> 20에서 50을 방문할 경우, 70 방문하는 경우로 재귀 함수 호출
    • 20 20 50 10 70 -> 70을 새로 방문 가능
    • 20 20 50 10 70 -> 더 방문할 곳이 없으므로 종료됨
• 해당 index를 방문할 때의 길이를 기록하여, 더 작은 부분수열로 방문하지 않도록 한다
  • A : 10 20 30 50 70  / i=4의 Length = 5 기록
  • B : 10 20 30 50 70  / i=4의 Length = 3 : 기록된 Length = 5보다 작으므로 방문하지 않음
• 일 때, 방문시 최대 길이를 기록해 둘 경우 Length = 5 에서만 방문하면 된다.
• 재귀함수로 구현하고, for loop를 사용한 호출이 끝난 후 최대 길이를 확인하여 기록한다.

void run(int idx, int current, int length)
{
	for (int i = idx; i < N; i++)
	{
		if (current < A[i] && visitLength[i] < length+1)
		{
			visitLength[i] = length + 1;
			run(i, A[i], length + 1);
		}
	}
	if (maxLength < length)
	{
		maxLength = length;
	}

}

전체 소스 코드

//Backjoon Problem No.11053
//https://www.acmicpc.net/problem/11053
//Mist16, 2022-03-01

#include <iostream>

using namespace std;

int A[1000]= { 0, };
int visitLength[1000] = { 0, };
int N = 0;

int maxLength = 0;

void run(int idx, int current, int length)
{
	for (int i = idx; i < N; i++)
	{
		if (current < A[i] && visitLength[i] < length+1)
		{
			visitLength[i] = length + 1;
			run(i, A[i], length + 1);
		}
	}
	if (maxLength < length)
	{
		maxLength = length;
	}

}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	run(0, 0, 0);
	cout << maxLength;

	return 0;
}

Note

• 조건을 검사하지 않고, 방문하지 않을 경우에도 재귀함수를 호출할 경우에는 O(n!)가 되어 시간 초과로 실패하는 문제였다.

문제

• 17070번 : 파이프 옮기기
• Rank : Gold V
• 링크 : https://www.acmicpc.net/problem/17070

풀이 전략

• 파이프는 좌, 하단, 좌하단대각선으로만 움직인다.
  • 파이프라인이 재귀될 염려가 없으므로, 파이프 이동선을 기억할 필요는 없다.
• 모든 경우의 수를 탐색하여, 가능한 경우의 수를 합산한다.

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

• 이 때, 같은 위치의 파이프 설치여부를 여러번 체크하게 되므로, 다이나믹 프로그래밍으로 풀이한다.
  • enum을 사용하여 각 상태를 정의해둔 후, 비트연산자 배열에 저장한다.
  • 타설가능 파이프 외에 검사했는지 여부를 확인하게 하여, 타설불가능 지역을 계속해서 체크하는 것을 방지한다.

int checkMap[16][16] = { 0, };
enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};
//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

전체 소스 코드

//Backjoon Problem No.17070
//Mist16, 2022-01-22

#include <iostream>

using namespace std;

enum pipeCond
{
	None = 0,
	Left = 1,
	LDown = 2,
	Down = 4,
	ConditionChecked = 8
};

int pipeMap[16][16] = { 0, };
int checkMap[16][16] = { 0, };
int N = 0;



//현재 위치에서 파이프 타설이 가능한지 체크
void checkConstructProb(int y, int x)
{
	int cond = pipeCond::ConditionChecked;
	//1. Left
	if (x + 1 < N)
	{
		if (pipeMap[y][x + 1] == 0)
			cond = cond | pipeCond::Left;
	}
	//2. Down
	if (y + 1 < N)
	{
		if (pipeMap[y + 1][x] == 0)
			cond = cond | pipeCond::Down;
	}
	//3. Left-Down
	if ((cond & pipeCond::Left) == (int)pipeCond::Left &&
		(cond & pipeCond::Down) == (int)pipeCond::Down)
	{
		if (pipeMap[y + 1][x + 1] == 0)
		{
			cond = cond | (int)pipeCond::LDown;
		}
	}
	checkMap[y][x] = cond;
}

//파이프 설치
int installPipe(int y, int x, int cond)
{
	int AllCases = 0;

	if (x == N-1 && y == N-1)
		return 1;

	if ((checkMap[y][x] & pipeCond::ConditionChecked) != pipeCond::ConditionChecked ) //unchecked, check
	{
		checkConstructProb(y, x);
	}
	//1. Left/LDown -> Left
	if (cond == pipeCond::Left || cond == pipeCond::LDown)
	{
		if((checkMap[y][x] & pipeCond::Left) == pipeCond::Left)
		{
			AllCases += installPipe(y, x + 1, pipeCond::Left);
		}
		
	}
	//2. Down/LDown -> Down
	if (cond == pipeCond::Down || cond == pipeCond::LDown)
	{
		if ((checkMap[y][x] & pipeCond::Down) == pipeCond::Down)
		{
			AllCases += installPipe(y + 1, x, pipeCond::Down);
		}
	}
	//3. All Cond -> LDown
	if ((checkMap[y][x] & pipeCond::LDown) == pipeCond::LDown)
	{
		AllCases += installPipe(y + 1, x + 1, pipeCond::LDown);
	}

	return AllCases;
}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//input n, pipemap;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> pipeMap[i][j];
		}
	}
	cout << installPipe(0, 1, pipeCond::Left);

	return 0;
}

여담

• 골드 하위권 문제까지는 빠르게 풀 수 있는 거 같다. 고난이도 문제에 도전해볼 것.