[Programmers] 안티세포

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

프로그래머스

 

a의 길이가 최대 20만이기 때문에 DP로 접근해야 하는 문제였습니다.

늦잠님 블로그 글을 참고하여 풀었습니다.

https://velog.io/@woolzam/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv.4Java-%EC%95%88%ED%8B%B0%EC%84%B8%ED%8F%AC

[프로그래머스/Lv.4][Java][C++] 안티세포

 

알고리즘은 다음과 같습니다.

1. 각 b 배열 (세그먼트)의 각 원소는 초기에는 개별 안티 세포로 존재하며, 아무 합성도 진행되지 않은 상태이므로 경우의 수는 1입니다.

 

2. 합성 선택 과정은 다음과 같습니다. (connect 함수)

• 현재 셀과 그 바로 왼쪽 셀의 값이 같은지 확인하여, 합성할 수 있는지 여부를 판단
• 합성이 가능할 경우 두 셀을 합쳐 값이 2배가 된 새로운 셀을 만들고, 재귀적으로 연쇄 합성 가능성을 고려하여 경우의 수 누적
• 합성하지 않았다면 이전 상태의 경우의 수를 그대로 이어받음

 

3. dp[i]에 각 단계까지의 누적 경우의 수를 저장하고 마지막에는 해당 세그먼트에서 가능한 모든 합성 결정의 경우의 수가 저장됩니다.

 

4. 파라미터로 전달되는 a는 여러 세그먼트로 나뉘어 있으므로, 각 세그먼트마다 위 과정을 독립적으로 수행한 뒤 최종 결과 dp[segmentEnd]를 반환합니다.

 

	#include <iostream>
	#include <vector>
	#include <map>
	using namespace std;
	const int MOD = 1e9 + 7;
	// “레벨 i”에서 각 셀(cell)의 값(merge 후 합)과
	// 그 값이 처음 등장한 이전 인덱스를 기록하는 map
	vector<map<long long, int>> levelMaps;
	// dp[i]는 “레벨 i”까지 진행했을 때 해당 상태에 도달할 수 있는 경우의 수
	vector<long long> dp;
	long long connect(long long cellValue, int currentIndex, int prevIndex)
	{
	// 현재 레벨에 cellValue가 기록되어 있지 않다면, (cellValue, prevIndex) 쌍을 등록
	if (levelMaps[currentIndex].find(cellValue) == levelMaps[currentIndex].end())
	{
	levelMaps[currentIndex][cellValue] = prevIndex;
	}
	// 우선 부모 셀(prevIndex)까지의 경우의 수로 초기화
	long long ways = dp[prevIndex];
	// 만약 바로 이전 레벨(prevIndex)에서 동일한 cellValue가 있었다면,
	// merge가 가능하므로, 해당 셀과 merge하여 cellValue가 2배가 된 경우의 수를 추가
	if (levelMaps[prevIndex].find(cellValue) != levelMaps[prevIndex].end())
	{
	int mergeOrigin = levelMaps[prevIndex][cellValue];
	ways = (ways + connect(cellValue * 2, currentIndex, mergeOrigin)) % MOD;
	}
	return ways;
	}
	vector<int> solution(vector<int> a, vector<int> s)
	{
	vector<int> answer;
	int totalSize = a.size() + 1;
	levelMaps.assign(totalSize, map<long long, int>());
	dp.assign(totalSize, 0);
	int segmentStart = 0;
	int segmentEnd = 0;
	for (int seg = 0; seg < s.size(); seg++)
	{
	int segmentLength = s[seg];
	segmentStart = segmentEnd;
	segmentEnd = segmentStart + segmentLength;
	// 세그먼트 시작 레벨 초기화
	// 레벨(인덱스) segmentStart는 초기 상태로, base 역할을 하며
	// dummy 값 (-1)을 기록해 이후 재귀의 기준
	levelMaps[segmentStart].clear();
	levelMaps[segmentStart][-1] = -1;
	dp[segmentStart] = 1;
	for (int i = segmentStart + 1; i <= segmentEnd; i++)
	{
	dp[i] = connect(a[i - 1], i, i - 1);
	}
	answer.push_back((int)(dp[segmentEnd] % MOD));
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE   

 

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