Mist16's Dev Blog

문제

• 1562번 : 계단 수
• Rank : Gold I
• 링크 : https://www.acmicpc.net/problem/1562

풀이 전략

• 모든 경우의 수를 구하는 문제
• 현재 수를 구할 필요는 없다(0~9까지의 숫자가 모두 등장하는지만을 확인하면 된다)
  • 비트마스킹으로 모든 수가 등장하는지를 확인한다.
• 0~8에서는 다음 수로, 1~9에서는 이전 수로 이동할 수 있다(9->0, 0->9는 불가능하다)
• 남은 인덱스, 현재 숫자, 비스마스크된 숫자를 함수 인자로 활용한다.
• unsigned long run(int lastDigit, int idx, unsigned int cBitMask)
• N의 값이 높을 경우 중복되는 함수 호출이 많아 속도를 확보하지 못하므로, 배열을 사용하여 메모이제이션해준다.
  • 답의 범위는 (0 ~ 999999999) * 2이므로, unsigned long으로 처리 가능하다.
    • *2 하는 이유는 경우의수를 구하는 과정에서 두 run의 값을 더하기 떄문이다.
  • bistmask : 0~1023, idx : 0~100, lastDigit : 0~9 이므로 1024*101*10 = 약 백만개의 변수를 사용한다.
    • 문제의 메모리 제한이 128MB이므로, 충분히 사용 가능하다.
  • 남은 숫자(idx)가 0이고, Digit이 모두 찬 경우(1023)는 경우의 수가 1이므로, 1로 선언하여둔다.
  • idx가 0인 나머지경우는 조건을 만족하지 못했으므로 0으로 처리하고, 남은 경우는 계산하여 저장한다.

전체 소스 코드

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

#include <iostream>

using namespace std;

unsigned int answerBitmask = 0b1111111111;

unsigned long answerBoard[1024][101][10] = { 0, };

void initialize()
{
	for (int i = 0; i <= 9; i++)
	{
		answerBoard[answerBitmask][0][i] = 1;
	}
}


unsigned long run(int lastDigit, int idx, unsigned int cBitMask)
{
	unsigned long answer = 0;
	if (answerBoard[cBitMask][idx][lastDigit] != 0)
		return answerBoard[cBitMask][idx][lastDigit];
	if (idx == 0)
		return 0;
	//+1
	if (lastDigit < 9)
	{
		answer += run(lastDigit + 1, idx - 1, cBitMask | (1 << (lastDigit + 1)));
	}
	//-1
	if (lastDigit > 0)
	{
		answer += run(lastDigit - 1, idx - 1, cBitMask | (1 << (lastDigit - 1)));
	}	
	answer = answer % 1000000000;
	answerBoard[cBitMask][idx][lastDigit] = answer;
	return answer;
}

int main()
{
	unsigned long long tAnswer = 0;
	unsigned long answer = 0;
	int N;
	cin >> N;

	initialize();

	for (int i = 1; i <= 9; i++)
	{
		answer += run(i, N - 1, (1 << i));
		answer = answer % 1000000000;
	}
	cout << answer;
	return 0;
}

Note

• 생각보다 큰 사이즈의 배열이라도 메모이제이션을 써야 할 경우가 있다.
  • 경우의 수는 크지만 실제 도출되는 계산의 양이 적은 경우는, STL map등을 사용하여 메모리를 절약할 수 있다.

문제

• 9663번 : N-Queen
• Rank : Gold V
• 링크 : https://www.acmicpc.net/problem/9663

풀이 전략

• 퀸의 경우 상하좌우, 대각선으로 길이 제한 없이 이동할 수 있다.
  
  • -> 한 줄에 퀸은 하나만 존재할 수 있다.
• 1~N번째 행까지, 퀸을을 놓을 수 있는 모든 열에 퀸을 두어서, 경우의 수를 모두 더한다.

int queenBoard(int idx, QueenBoard qBoard)
{
	int answer = 0;

	if (idx == N)
		return 1;
	for (int i = 0; i < N; i++)
	{
    	answer += queenBoard(idx + 1, tempBoard);
	}
    return answer;
}

• 대각선 / 다른 행에 다른 줄의 퀸이 있을 경우 퀸을 놓을 수 없으므로, 퀸을 둘 때마다 보드에 해당 범위를 체크한다.
  • int [N][N]으로 구현할 경우 함수 호출 인자가 지나치게 기므로, 비트마스킹으로 구현하였다.
  • 퀸을 놓기 전, 해당 칸의 비트마스크가 0인지 확인하고, 0일 경우에 해당 퀸에 영향을 받는 칸을 비트마스킹 한 후 함수를 재귀 호출해준다.
  • 비트마스킹해야할 사항은 다음과 같다
    • Queen을 놓은 곳의 가로선
    • Queen을 놓은 곳으로부터의 대각선(X모양)

if ((qBoard.n[i] & (1 << idx)) == 0)
{
	QueenBoard tempBoard = qBoard;
	tempBoard.n[i] = tempBoard.n[i] | (1 << idx);
	for (int j = 1; j < N - idx; j++)
	{
		tempBoard.n[i] = tempBoard.n[i] | (1 << (idx+j));
	
		if (i - j >= 0)
		{
			tempBoard.n[i - j] = tempBoard.n[i - j] | (1 << (idx + j));
		}
		if (i + j < N)
		{
			tempBoard.n[i + j] = tempBoard.n[i + j] | (1 << (idx + j));
		}
	}
}

전체 소스 코드

//Backjoon Problem No.09663
//https://www.acmicpc.net/problem/9663
//Mist16, 2022-02-06
#include <iostream>

using namespace std;

int N;

struct QueenBoard
{
	unsigned int n[15] = { 0, };
};

int queenBoard(int idx, QueenBoard qBoard)
{
	int answer = 0;

	if (idx == N)
		return 1;
	for (int i = 0; i < N; i++)
	{
		if ((qBoard.n[i] & (1 << idx)) == 0)
		{
			QueenBoard tempBoard = qBoard;
			tempBoard.n[i] = tempBoard.n[i] | (1 << idx);
			for (int j = 1; j < N - idx; j++)
			{
				tempBoard.n[i] = tempBoard.n[i] | (1 << (idx+j));
				
				if (i - j >= 0)
				{
					tempBoard.n[i - j] = tempBoard.n[i - j] | (1 << (idx + j));
				}
				if (i + j < N)
				{
					tempBoard.n[i + j] = tempBoard.n[i + j] | (1 << (idx + j));
				}
			}
			answer += queenBoard(idx + 1, tempBoard);
		}
	}
	return answer;
}


int main()
{
	QueenBoard blankboard;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	cout << queenBoard(0, blankboard);
	
	return 0;
}

Note

• 비트마스킹을 쓰지 않을 경우 시간 초과로 실패하였다. 함수 호출이 잦을 경우, 함수로 전달되는 인자의 양에도 신경을 써야 할 것.