문제

 

1562번: 계단 수

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

풀이 전략

  • 모든 경우의 수를 구하는 문제
  • 현재 수를 구할 필요는 없다(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등을 사용하여 메모리를 절약할 수 있다.

'Problem Solving > Backjoon' 카테고리의 다른 글

[백준][C++]9465 - 스티커  (0) 2022.03.14
[백준][C++]1036 - 36진수  (0) 2022.03.08
[백준][C++]1043 - 거짓말  (0) 2022.03.03
[백준][C++]9663 - N-Queen  (0) 2022.03.02
[백준][C++]11053 - 가장 긴 증가하는 부분 수열  (0) 2022.03.01

문제

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

풀이 전략

  • A^n = A^(n/2) * A^(n/2) 인 점을 이용하여, 분할 정복한다.
  • 분할 정복으로 곱셈 문제를 해결할 경우 중복된 계산이 많이 발생하므로, 제곱 계산의 결과를 메모이제이션하여 중복된 계산을 생략한다.
  • 이 때, N이 최대 100,000,000,000이고 분할당 1/2으로 감소하므로, Array 대신 Map을 사용하여 결과를 저장하도록 한다.

전체 소스 코드

더보기 
//Backjoon Problem No.10830
//https://www.acmicpc.net/problem/10830
//Mist16, 2022-02-05
#include <iostream>
#include <map>

using namespace std;

unsigned int N = 0;
unsigned long long B = 0;

struct matrix
{
	unsigned int mat[5][5];

	matrix()
	{
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				mat[i][j] = 0;
	}
};

map<unsigned long long, matrix> dices;

matrix matrixMulti(const matrix& a, const matrix& b)
{
	matrix temp;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			unsigned int tempv = 0;
			for (int k = 0; k < N; k++)
			{
				tempv = tempv + (a.mat[i][k] * b.mat[k][j]);
			}
			tempv = tempv % 1000;
			temp.mat[i][j] = tempv;

		}
	}
	return temp;
}

matrix getNSquare(unsigned long long n)
{
	auto iter = dices.find(n);

	if (iter == dices.end())
	{
		unsigned long long a, b;
		a = n / 2;
		b = n - a;
		matrix tempmat;
		tempmat = matrixMulti(getNSquare(a), getNSquare(b));
		dices.insert(pair <unsigned long long, matrix>(n, tempmat));
		return tempmat;

	}
	return iter->second;
}

void run()
{
	matrix result = getNSquare(B);
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << result.mat[i][j] % 1000 << " ";
		}
		cout << endl;
	}
	return;
}

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

	matrix temp;
	
	cin >> N >> B;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> temp.mat[i][j];
		}
	}

	dices.clear();
	dices.insert(pair <unsigned long long, matrix>(1, temp));

	run();

	return 0;
}

풀이 중 주의 사항

  • N의 범위가 0 ~ 100,000,000,000이므로, 충분히 큰 변수 형태를 사용하여 저장한다.
  • 행렬의 구성요소가 1000으로 입력되고, 제곱연산을 하지 않을 경우에도 0으로 출력해야 하는 점을 주의하도록 한다.

'Problem Solving > Backjoon' 카테고리의 다른 글

[백준][C++]9663 - N-Queen  (0) 2022.03.02
[백준][C++]11053 - 가장 긴 증가하는 부분 수열  (0) 2022.03.01
[백준][C++]1007 - 벡터 매칭  (0) 2022.01.25
[백준][C++]17070 - 파이프 옮기기 1  (0) 2022.01.22
[백준][C++]1202 - 보석 도둑  (0) 2022.01.21

+ Recent posts

티스토리툴바