[99클럽/코딩테스트 챌린지/C++] 밤양갱 문제 해결 방법

문제 링크 : 

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

문제 요약

목표: daldidalgo라는 문자열을 총 N번 반복 입력한 후 마지막에 daldidan으로 끝내는 문자열을 최소 시간 내에 완성해야 한다.

제약:

• 문자 하나씩 입력하거나, 이미 입력한 문자열을 복사해 붙여넣는 두 가지 작업만 가능.
• 시간 복잡도 효율화를 위해 복사-붙여넣기를 활용하여 빠르게 반복 횟수를 채워야 한다.

문제 해결 아이디어

1, 첫 번째 문자열 입력:

• "daldidalgo"를 처음 입력하는 데 8초가 걸린다고 가정.
• 이 입력 후 복사-붙여넣기 작업을 통해 최대한 빠르게 문자열을 확장해 나가는 방식으로 최적화 가능.

2, 복사-붙여넣기 최적화:

• 복사-붙여넣기 작업으로 현재까지 입력된 daldidalgo의 수를 2배로 늘릴 수 있을 때마다, 복사 횟수를 줄이기 위해 복사를 진행.
• 복사-붙여넣기 작업을 통해 현재 횟수가 N에 도달할 수 있도록 반복한다.

3, 마무리 작업:

• 마지막 "daldidan"을 추가하여 완성하는 데 추가 1초가 필요함.

코드

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <map>
#include <queue>

using namespace std;

int main() {
	int N = 0;
	std::cin >> N;  // 반복 횟수 N 입력 받기

	// N이 1일 경우, "daldidalgo" 하나만 입력하면 되므로 10초 소요
	if (N == 1)
	{
		// daldi = > 5
		// daldi + dal = > 6
		// daldidal + go = > 8
		// daldidalgo + daldida => 9
		// daldidalgodaldida + n => 10
		std::cout << 10 << '\n';
	}
	// N이 2일 경우, "daldidalgo" 하나 입력 후 하나 더 추가하여 총 11초 소요
	else if (N == 2)
	{
		// daldi = > 5
		// daldi + dal = > 6
		// daldidal + go = > 8
		// daldidalgo + daldidalgo => 9
		// daldidalgo + daldida => 10
		// daldidalgodaldida + n => 11
		std::cout << 11 << '\n';
	}
	// N이 3 이상일 경우 최적의 복사 작업을 통해 시간을 계산
	else
	{
		int count = 0;  // 작업 횟수를 카운트할 변수
		int daldidalgoCount = 1;  // 현재까지 입력된 "daldidalgo" 횟수

		// 반복문을 통해 "daldidalgo"를 복사하여 N에 도달할 때까지 횟수를 증가
		while (daldidalgoCount <= N)
		{
			// 남은 필요 횟수가 현재 횟수의 두 배 이상인 경우
			// 복사하여 "daldidalgo" 횟수를 두 배로 늘리고 카운트를 1 증가
			if (daldidalgoCount * 2 <= N) {
				daldidalgoCount *= 2;
				count++;
			}
			// 남은 필요 횟수가 현재 횟수보다 적거나 같을 경우, 추가 작업을 완료하고 종료
			else
			{
				// 지금까지 추가한 daldidalgo를 남은 갯수만큼 추가하는 작업 => 1
				// "daldidan"을 추가하는 작업 => 1
				count += 2;  // + 2
				break;
			}
		}
		// 첫 번째 "daldidalgo"를 입력하는 데 소요되는 8초 추가
		// + daldidal => 8;
		count += 8;
		std::cout << count << '\n';  // 최종 최소 시간 출력
	}

	return 0;
}

코드 풀이

• N = 1일 경우: daldidalgo만 입력 → 총 10초 소요.
• N = 2일 경우: daldidalgo 한 번 입력 후 복사 → 총 11초 소요.
• N >= 3일 경우: 첫 "daldidalgo"를 8초에 입력 후 복사 최적화 → 최소 시간을 계산.

배운 점

• 효율적인 반복 처리: 반복적인 문자열 입력을 최적화하기 위해 복사-붙여넣기 작업을 활용하여 빠르게 문자열을 늘리는 방법을 익혔다.
• 그리디 알고리즘의 활용성: 이 문제를 통해, 매 순간 최적의 선택을 하는 그리디 방식을 적용하여 최소 시간을 도출할 수 있다는 것을 배웠다.
• 조건문과 반복문의 조합: 간단한 조건문으로 특수 케이스(N = 1, N = 2)를 빠르게 처리하고, 일반적인 경우에 대해서는 반복문을 통해 효율적인 해결책을 찾는 방식이 유용하다는 점을 깨달았다.

결론

이번 문제는 복사-붙여넣기를 최적화하여 반복되는 작업을 최소화함으로써 최적의 해결 시간을 구하는 접근법을 연습할 수 있었다. 특히, 문자열을 하나씩 입력하는 대신 최대한 반복을 활용할 때 효율적인 알고리즘이 필요하다는 점을 깨달았다. 앞으로 복사-붙여넣기와 같은 반복적인 최적화 문제에서 그리디 알고리즘을 적용할 때 유사한 패턴을 활용할 수 있을 것이다.