[Programmers] 카운트 다운

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/131129#

프로그래머스

 

target이 최대 10만 점이고 다트는 한 턴당 최대 60점을 얻을 수 있기 때문에 단순 구현으로 접근하면 TLE가 발생합니다.

따라서 DP로 풀어야하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. cache 벡터를 0 인덱스이므로 크기는 target + 1만큼 그리고 모든 인덱스를 {0, 0}으로 초기화해줍니다.

2. 모든 경우의 수를 확인하기 위해 모든 케이스에 대해 다트를 던져보고 가능한 케이스일 경우 cache를 업데이트해 줍니다.

2.1 여기서 불가능한 케이스의 여부는 크게 세 가지로 판단하며 아래 조건에 해당하지 않을 경우 가능하다고 판단합니다.

2.1.1 다트를 던졌을 때 점수가 0 미만이 될 경우 불가능한 케이스로 판단합니다.

2.1.2 다트를 던졌는데도 불구하고 던지기 전 cache에 저장된 던진 횟수와 같거나 적다면 모순이므로 불가능한 케이스로 판단합니다.

2.1.3 다트를 던진 횟수가 딱 한 번 차이 나고 "싱글" 또는 "불"을 맞춘 횟수를 업데이트하기 전인 상태인데 이미 "싱글" 또는 "불"을 맞춘 횟수가 업데이트 전 cache보다 높을 경우 모순이므로 불가능한 케이스로 판단합니다.

2.2 2.1.1 ~ 2.1.3 조건들에 해당하지 않을 경우 가능한 케이스로 판단해 cache를 업데이트합니다.

3. 2번 과정을 통해 도출해 낸 최종 결과를 반환해 줍니다.

 

	#include <string>
	#include <vector>
	#include <iostream>
	using namespace std;
	const int MAX = 1e5 + 1;
	const int FINAL_SCORE = 0;
	typedef struct
	{
	int cnt;
	int bullOrSingleCnt;
	} State;
	vector<State> cache;
	bool isPossible(int nextTotal, int total)
	{
	if (nextTotal < 0)
	{
	return false;
	}
	if (cache[nextTotal].cnt
	&& cache[nextTotal].cnt <= cache[total].cnt)
	{
	return false;
	}
	if (cache[nextTotal].cnt == cache[total].cnt + 1
	&& cache[nextTotal].bullOrSingleCnt > cache[total].bullOrSingleCnt)
	{
	return false;
	}
	return true;
	}
	vector<int> solution(int target) {
	cache.resize(target + 1, {0, 0});
	for (int total = target; total > 0; total--)
	{
	for (int multiple = 1; multiple <= 3; multiple++)
	{
	for (int score = 1; score <= (multiple == 1 ? 50 : 20); score += (multiple == 1 && score == 20) ? 30 : 1)
	{
	int nextTotal = total - (score * multiple);
	if (!isPossible(nextTotal, total))
	{
	continue;
	}
	cache[nextTotal].cnt = cache[total].cnt + 1;
	cache[nextTotal].bullOrSingleCnt = (multiple == 1)
	? cache[total].bullOrSingleCnt + 1 : cache[total].bullOrSingleCnt;
	}
	}
	}
	return {cache[FINAL_SCORE].cnt, cache[FINAL_SCORE].bullOrSingleCnt};
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~