알고리즘 문제해결 전략(문제 ID: MORSE)

OvO·2020년 7월 17일
0

문제해결전략

목록 보기
2/16

문제

모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 들어 알파벳 J는 모스 부호 o---로 표현되고, M은 --로 표현됩니다.
n개의 장점과 m개의 단점으로 구성된 모든 신호들을 담고 있는 사전이 있다고 합시다. 예를 들어 n = m = 2라면 다음과 같은 신호들이 포함되어 있는 것이죠.

이 신호들은 사전순서대로 정렬되어 있습니다. -의 아스키 코드는 45이고, o의 아스키 코드는 111이기 때문에 -가 먼저 오게 되죠. n과 m이 주어질 때 이 사전의 k번째 신호를 출력하는 프로그램을 작성해 봅시다. 예를 들어 위 사전에서 네 번째 신호는 o--o입니다.

입력
입력의 첫 줄에는 테스트 케이스의 수 C(≤50)가 주어집니다. 각 테스트 케이스는 세 개의 정수 n, m(1≤n, m≤100), k(1≤k≤1,000,000,000)로 주어집니다. 사전에는 항상 k개 이상의 신호가 있다고 가정해도 좋습니다.

출력
각 테스트 케이스마다 한 줄에 해당 신호를 출력합니다.

예제 입력
3
2 2 4
4 8 13
6 4 1

예제 출력
o--o
--o-ooo-oooo
------oooo

🤔첫생각

이 책에서 보던 DP문제랑 사뭇다른 형태의 문제로 느껴졌다. 그래서 왜 이 문제가 왜 DP인지 의아했었다. 사전을 직접 만들어보면서 어떤 규칙으로 작동하는지를 생각했다. 현재 k번째일때 가장 오른쪽에있는 morse[idx]는 'o'이고 morse[idx-1]은 '-'을 만족하는 idx를 찾은후, idx의 'o'를 왼쪽으로 한 칸 옮기고 idx보다 오른쪽에 있는 'o'를 맨 우측으로 이동시키면 된다. 하지만 이런 방식은 너무 단순하여 k가 10억이 될 수 있으므로 시간안에 못 풀 것이라 생각했고, 그래서 DP를 활용할 방법을 생각했다. 그렇게 떠올린 방법이 이항계수를 활용해서 쓸데없는 연산을 줄인것이다. 또한 이렇게 하면 정답을 구하는 과정에서 옮겨야 될 'o'보다 오른쪽에 있는 'o'들은 항상 맨 우측에 있는 셈이므로(처음에 ---ooo으로 시작하기 때문)더욱 효율적이었다.

😯부족했던 부분

처음 코드를 작성했을 때 별 다른 문제를 발견하지 못하고 제출을 했었다. 하지만 채점 결과는 오답이었다. 어디가 틀렸는지 확인하려고 몇 가지 예시를 돌려봤는데 50 50 2처럼 이항계수가 큰 숫자들이 나올경우 overflow가 발생한다는 문제점이 있었다. 문제 조건에서 k가 10억 이하라는 조건이 있었기 때문에 이항계수가 10억 보다 큰 숫자가 나오면 10억 + 1로 처리 함으로 써 overflow를 해결했지만 처음부터 overflow를 고려하지 않았던 부분이 부족하다고 생각한다.

😀코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int n, m, k;
int morse[200];	//o->1, - -> 0
int	cache[200][200];

int combination(int n, int r) {
	if (n == r || r == 0)
		return 1;

	int& ret = cache[n][r];
	
	if (ret != 0)
		return ret;
	
	ret = combination(n - 1,r - 1) + combination(n - 1,r);
	if (ret > 1000000000)	//overflow가 발생하는 걸 막기위해서
		ret = 1000000001;
	return ret;
}

void objMorse(int currentNum) {
	if (currentNum == k)
		return;
	
	int here = n + m - 1;
	int cnt1 = 0;

	while (!(morse[here - 1] == 0 && morse[here] == 1)) {
		if (morse[here] == 1)
			cnt1++;
		here--;
	}

	cnt1++;

	for (int to = 0; to < here; to++) {
		int tmp = combination(here - to - 1 + cnt1, cnt1);
		if (k >= currentNum + tmp) {
			morse[here] = 0;
			morse[to] = 1;
			objMorse(currentNum + tmp);
			return;
		}
	}
}

int main(void) {
	int C;

	cin >> C;

	for (int i = 0; i < C; i++) {
		cin >> n >> m >> k;
		
		memset(morse, 0, sizeof(morse));

		for (int j = n; j < n + m; j++)
			morse[j] = 1;
		
		objMorse(1);

		for (int j = 0; j < n + m; j++) {
			if (morse[j] == 0)
				printf("-");
			else
				printf("o");
		}
		printf("\n");
	}

	return 0;
}

👏후기

이 책의 코드와 나의코드를 비교했을 때 이항계수를 활용한다는 점에서 공통점이 있지만 책의 코드가 더욱 논리적이라는 생각이든다. 그만큼 나의 코드가 조잡하다는 소리이다. 부정적으로 나는 아직 부족하다고 생각할 수 있겠지만 긍정적으로 생각하면 더 발전할 여지가 남아있다고 생각할 수 도 있다.👍

profile
이유재입니다.

0개의 댓글