[백준/15312] 이름 궁합

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/15312

15312번: 이름 궁합

 

2) 설명

 그냥 영어 이름 궁합 보는 문제다.

여자친구랑 이름 궁합 봐보려고 풀어봤는데 궁합 정확도가 상당히 떨어지는 것 같다.

 

2. 풀이

1) 알고리즘

    : 단순 구현

 

2) 풀이 설명

재귀를 사용해서 풀어보았다.

그냥 원소 두 개 남을 때까지 이웃 원소들의 합 벡터( (1,2), (2,3), (3,4), ... , (N-1,N)를 반환하는 함수를 계속 재귀 호출했다.

 

3. 코드

/*
	이름 궁합
	단순 구현
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solve(vector<int> nums){
	if(nums.size() == 2)
		return nums;
	vector<int> answer;
	for(int i=0;i<(int)nums.size()-1;i++)
		answer.push_back((nums[i]+nums[i+1])%10);

	return solve(answer);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	vector<int> cnt = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1};

	string jm, jh;
	cin >> jm >> jh;
	
	vector<int> nums;
	for(int i=0;i<jm.length();i++){
		nums.push_back(cnt[jm[i] - 'A']);
		nums.push_back(cnt[jh[i] - 'A']);
	}
	vector<int> result = solve(nums);
	for(auto r : result)
		cout << r;
	cout << endl;

	return 0;
}

 

4. 느낀점

- 재귀로 한번 풀어봤는데 비효율적이다.(시간적, 공간적 모두) 그렇지만 재미삼아 푼 문제라서 그냥 내비뒀다.

 -> 반복문으로 두 개씩 줄여가도록 풀면 빨라진다.