백준 2780번 비밀번호 C++ 구현해보기

---

```

백준 2780번 비밀번호 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 번호 2780번 풀이
2.  DP 연습

---

https://www.acmicpc.net/problem/2780

 

 

 

백준 2780번은 

난이도 중급 등급의 문제로서

 

0부터 9 까지 입력가능한

비밀번호 패드가 주어질때

 

1.  위 그림에서 인접한 번호만 누를수 있음

예)

(1이면 2,4)

(0이면 7)

(5면 2,4,6,8)

2. 가능한 비밀번호 전체 개수를 출력해야 하며

 

값이 매우 크기 떄문에 1234567로 나눈 나머지를 출력해야 합니다.

 

DP를 배울수 있는 좋은 문제이며

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

먼저 1002에 10 인 2중 배열을 전역으로 선언해주고 -1로 채워주었습니다.

int32_t memoization[1002][10] = {-1};
std::fill(&memoization[0][0], &memoization[1002][0], -1);

 

테스트케이스를 입력받고

테스트 케이스만큼 해당되는 비밀번호 자릿수를 입력받습니다.

	std::cin.tie(NULL); 
	std::ios::sync_with_stdio(false);

	std::string inputStr;
	std::getline(std::cin, inputStr);
	const int32_t testCaseCnt = stoi(inputStr);

	for (int32_t i = 0; i < testCaseCnt; i++)
	{
		std::getline(std::cin, inputStr);
		const int32_t pwCnt = stoi(inputStr);
		std::cout << findPossibility(pwCnt) << "\n";
	}

0부터9까지의 경우의 수를 모두 더해주고

재귀적으로

동적 계획법(DP)함수에 넣어줍니다.

int32_t findPossibility(int32_t cnt)
{
	int32_t ret = 0;

	for (int i = 0; i < 10; i++)
	{
		ret += findVal(cnt, i);
		ret = ret % 1234567;
	}

	return ret;
}

 

cnt 카운트 값이 재귀를 반복하면서 -1씩 작아지고

각 카운트와 숫자에 대한 값을 찾아서 더해줍니다.

값을 계산후에 모듈러 함수로 1234567로 나누어주고

 

동적계획법에 단골로 등장하는 메모아이제이션 배열로 중간 값을 저장합니다(아까 1002에 10짜리 배열)

 

값을 리턴해줍니다.

키패드에 인접한 숫자만큼 케이스문을 넣어서 더해주었습니다.

 

int32_t findVal(int32_t cnt, int32_t num)
{
	int32_t ret = 0;


	if (cnt == 1 || cnt == 0)
	{
		ret += 1;
	}
	else if (memoization[cnt][num] != -1)
	{
		return memoization[cnt][num];
	}
	else
	{
		switch (num)
		{
		case 0:
		{
			ret += findVal((cnt -1), 7);
			break;
		}
		case 1:
		{
			ret += findVal((cnt - 1), 2);
			ret += findVal((cnt - 1), 4);
			break;
		}
		case 3:
		{
			ret += findVal((cnt - 1), 2);
			ret += findVal((cnt - 1), 6);
			break;
		}
		case 9:
		{
			ret += findVal((cnt - 1), 6);
			ret += findVal((cnt - 1), 8);
			break;
		}
		case 2:
		{
			ret += findVal((cnt - 1), 1);
			ret += findVal((cnt - 1), 3);
			ret += findVal((cnt - 1), 5);
			break;
		}
		case 4:
		{
			ret += findVal((cnt - 1), 1);
			ret += findVal((cnt - 1), 5);
			ret += findVal((cnt - 1), 7);
			break;
		}
		case 6:
		{
			ret += findVal((cnt - 1), 3);
			ret += findVal((cnt - 1), 5);
			ret += findVal((cnt - 1), 9);
			break;
		}
		case 7:
		{
			ret += findVal((cnt - 1), 4);
			ret += findVal((cnt - 1), 8);
			ret += findVal((cnt - 1), 0);
			break;
		}
		case 8:
		{
			ret += findVal((cnt - 1), 5);
			ret += findVal((cnt - 1), 7);
			ret += findVal((cnt - 1), 9);
			break;
		}
		case 5:
		{
			ret += findVal((cnt - 1), 2);
			ret += findVal((cnt - 1), 4);
			ret += findVal((cnt - 1), 6);
			ret += findVal((cnt - 1), 8);
			break;
		}
		}
	}

	ret = ret % 1234567;
	memoization[cnt][num] = ret;
	return ret;
}

 

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>

int32_t findPossibility(int32_t cnt);
int32_t findVal(int32_t cnt, int32_t num);
int32_t memoization[1002][10] = {-1};


int32_t findPossibility(int32_t cnt)
{
	int32_t ret = 0;

	for (int i = 0; i < 10; i++)
	{
		ret += findVal(cnt, i);
		ret = ret % 1234567;
	}

	return ret;
}

int32_t findVal(int32_t cnt, int32_t num)
{
	int32_t ret = 0;


	if (cnt == 1 || cnt == 0)
	{
		ret += 1;
	}
	else if (memoization[cnt][num] != -1)
	{
		return memoization[cnt][num];
	}
	else
	{
		switch (num)
		{
		case 0:
		{
			ret += findVal((cnt -1), 7);
			break;
		}
		case 1:
		{
			ret += findVal((cnt - 1), 2);
			ret += findVal((cnt - 1), 4);
			break;
		}
		case 3:
		{
			ret += findVal((cnt - 1), 2);
			ret += findVal((cnt - 1), 6);
			break;
		}
		case 9:
		{
			ret += findVal((cnt - 1), 6);
			ret += findVal((cnt - 1), 8);
			break;
		}
		case 2:
		{
			ret += findVal((cnt - 1), 1);
			ret += findVal((cnt - 1), 3);
			ret += findVal((cnt - 1), 5);
			break;
		}
		case 4:
		{
			ret += findVal((cnt - 1), 1);
			ret += findVal((cnt - 1), 5);
			ret += findVal((cnt - 1), 7);
			break;
		}
		case 6:
		{
			ret += findVal((cnt - 1), 3);
			ret += findVal((cnt - 1), 5);
			ret += findVal((cnt - 1), 9);
			break;
		}
		case 7:
		{
			ret += findVal((cnt - 1), 4);
			ret += findVal((cnt - 1), 8);
			ret += findVal((cnt - 1), 0);
			break;
		}
		case 8:
		{
			ret += findVal((cnt - 1), 5);
			ret += findVal((cnt - 1), 7);
			ret += findVal((cnt - 1), 9);
			break;
		}
		case 5:
		{
			ret += findVal((cnt - 1), 2);
			ret += findVal((cnt - 1), 4);
			ret += findVal((cnt - 1), 6);
			ret += findVal((cnt - 1), 8);
			break;
		}
		}
	}

	ret = ret % 1234567;
	memoization[cnt][num] = ret;
	return ret;
}



int main()
{
	std::fill(&memoization[0][0], &memoization[1002][0], -1);

	std::cin.tie(NULL); 
	std::ios::sync_with_stdio(false);

	std::string inputStr;
	std::getline(std::cin, inputStr);
	const int32_t testCaseCnt = stoi(inputStr);

	for (int32_t i = 0; i < testCaseCnt; i++)
	{
		std::getline(std::cin, inputStr);
		const int32_t pwCnt = stoi(inputStr);
		std::cout << findPossibility(pwCnt) << "\n";
	}
}

 

입력/출력

10
1
10
3
74
999
1173907
1000
689038
13
166272
14
112932
50
863504
60
1191588
70
304117
80
603034

 

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---