- BFS를 사용할 줄 안다
- DFS를 사용할 줄 안다
- DP를 사용할 줄 안다
- 행은 클립보드에 있는 이모티콘 개수, 열은 현재 화면의 이모티콘 개수에 대한 시간을 저장하기 위해 이차원 배열을 생성한다
- 배열을 최대 시간으로 모두 초기화 해준다
- 우선 무조건 1번의 복사는 필요하기에, 배열[1][1] = 1 으로 초기화 해준다
- DFS를 사용, 3가지 케이스에 대해서, 배열에 대한 시간이 더 적다면 초기화 해주고 재귀함수를 실행해준다.
#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;
int answer = 987654321;
//클립보드 수, 현재 수
int arr[1001][1001];
//클립보드수, 현재 상황이 같은데 횟수가 더 크면 그만둠
void dfs(int ClipBoard, int Now_Numbers, int Now_Cnt)
{
if (Now_Cnt > 500 || Now_Numbers > 1000 || ClipBoard > 1000) return;
int New_Cnt = Now_Cnt + 1;
//클립보드 저장
int New_Clip_Board = Now_Numbers;
if (New_Clip_Board <= 1000)
{
if (arr[New_Clip_Board][Now_Numbers] > New_Cnt)
{
arr[New_Clip_Board][Now_Numbers] = New_Cnt;
dfs(New_Clip_Board, Now_Numbers, New_Cnt);
}
}
int New_Now_Numbers = Now_Numbers + ClipBoard;
if (New_Now_Numbers <= 1000)
{
if (arr[ClipBoard][New_Now_Numbers] > New_Cnt)
{
arr[ClipBoard][New_Now_Numbers] = New_Cnt;
dfs(ClipBoard, New_Now_Numbers, New_Cnt);
}
}
int Erased_Numbers = Now_Numbers - 1;
if (Erased_Numbers > 0)
{
if (arr[ClipBoard][Erased_Numbers] > New_Cnt)
{
arr[ClipBoard][Erased_Numbers] = New_Cnt;
dfs(ClipBoard, Erased_Numbers, New_Cnt);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int s; cin >> s;
for (int i = 1; i <= 1000; i++)
{
for (int j = 1; j <= 1000; j++)
{
arr[i][j] = 9999;
}
}
//1개 복사하고, 1개 남아있을때를 초기화 == 1
arr[1][1] = 1;
dfs(1, 1, 1);
for (int i = 1; i <= 1000; i++)
{
if (answer > arr[i][s]) answer = arr[i][s];
}
cout << answer;
return 0;
}
DP를 어떤식으로 사용하는 줄 안다면 충분히 풀 수 있는 쉬운 문제.
저는 DFS로 풀었으나, 다른 풀이들을 참고해 보았을 때 queue를 사용해서 BFS로 푸는 편이 시간 측면에서 훨씬 줄일 수 있을꺼 같습니다.
최단시간을 구하는 것은 BFS를 사용한다는 것을 인지해야할 것 같습니다.