백준[14226] 이모티콘 풀이 C++

Nilo의 개발 일지·2021년 8월 1일
0

알고리즘

목록 보기
4/29
post-custom-banner

백준[14226] 이모티콘

아이디어

  • BFS를 사용할 줄 안다
  • DFS를 사용할 줄 안다
  • DP를 사용할 줄 안다

접근방식

  1. 행은 클립보드에 있는 이모티콘 개수, 열은 현재 화면의 이모티콘 개수에 대한 시간을 저장하기 위해 이차원 배열을 생성한다
  2. 배열을 최대 시간으로 모두 초기화 해준다
  3. 우선 무조건 1번의 복사는 필요하기에, 배열[1][1] = 1 으로 초기화 해준다
  4. 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를 사용한다는 것을 인지해야할 것 같습니다.

  • 배울것
    1) 최단시간 구하는 DP는 [BFS]를 우선 생각하자!!
profile
프론트와 알고리즘 저장소
post-custom-banner

0개의 댓글