[Week 6] MORSE self review - Yunhyunjo

[Yunhyunjo]

MORSE self review

1. 해결 시도 과정

처음에는 모든 경우의 수를 다 돌아가며 값을 구하려고 하였습니다. 하지만 어떻게 순서대로 구해야할지 감이 오지 않아 다른 사람의 풀이를 통해 이항계수공식을 활용하여 접근하면 된다는 것을 파악했습니다.

2. 아이디어

이항계수는 dp를 활용하여 일단 모든 값을 구했습니다.

3. 코드 설명

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int n, m, k;
int bino[201][201];

void setBino();
void createString(int n, int m, string s);

int main(void) {
	int c;
	cin >> c;

	while (c--) {
		cin >> n >> m >> k;
		setBino();

		if (bino[n + m - 1][n - 1] > k--)
			createString(n-1,m,"-");
		else
			createString(n, m-1, "o");
	}
}

void setBino() {

	for (int i = 0; i < 201; i++) {
		bino[i][0] = bino[i][i] = 1;
	}

	for (int i = 2; i < 201; i++) {
		for (int j = 1; j < i; j++) {
			bino[i][j] = min(1000000000, bino[i - 1][j - 1] + bino[i - 1][j]);
		}
	}
}

void createString(int n, int m, string s) {

	if (k < 0)
		return;

	if (k == 0) {
		cout << s << "\n";
		k--;
		return;
	}

	if (k <= bino[n][m]) {
		createString(n - 1, m, s + '-');
	}
}

dp를 통해 이항계수의 값을 미리 다 구해놓았습니다.

4. 막힌 점 및 개선 사항

구해놓은 이항계수를 통해 값을 찾고자하는 값을 구하는 부분에서 막혔습니다. 다시 더 생각해 보아야 될 것 같습니다.