[COS Pro] 1급 3차 C++ (소수)

66분 

 

문제4)ㅇㄴㄹㄴㅇ

두 문자열 s1과 s2를 붙여서 새 문자열을 만들려 합니다. 이때, 한 문자열의 끝과 다른 문자열의 시작이 겹친다면, 겹치는 부분은 한 번만 적습니다.

예를 들어 s1 = "ababc", s2 = "abcdab"일 때, 아래와 같이 s1 뒤에 s2를 붙이면 새 문자열의 길이는 9입니다.

그러나 s2 뒤에 s1을 붙이면 새 문자열의 길이는 8로, 더 짧게 만들 수 있습니다.

두 문자열 s1과 s2가 매개변수로 주어질 때, s1과 s2를 붙여서 만들 수 있는 문자열 중, 가장 짧은 문자열의 길이를 return 하도록 solution 함수를 완성해주세요.

제한 조건
두 문자열 s1과 s2가 solution 함수의 매개변수로 주어집니다.

* s1과 s2의 길이는 1 이상 100 이하입니다.
* s1과 s2는 알파벳 소문자로만 이루어져 있습니다.

 

---

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int cmp(string arr1, string arr2) {
	vector<int> v;
	int length = min(arr1.size(), arr2.size());
	
	for(int i=0; i<arr1.size(); i++) {
		if(arr1[i] == arr2.front()) {
			int idx = i;
			for(int j=0; j<arr1.size()-i; j++) {
				if(arr1[idx+j] == arr2[j]) {
					if(idx+j == arr1.size()-1) v.push_back(i);
					continue;
				}
				else break;
			}
		}
	}
	return v.back();
}
int solution(string s1, string s2) {
    
    int answer = 0;
	  int cmp1 = s1.size() - cmp(s1,s2);
	  int cmp2 = s2.size() - cmp(s2,s1);
	
		if(cmp1 > cmp2) {
			answer = s1.size() + s2.size() - cmp1;
		} else answer = s1.size() + s2.size() - cmp2;
	
    return answer;
}

---

난 왜이렇게 간단하게 못 풀었는가

 

#include <string>
#include <vector>

using namespace std;

int overlap(string s1, string s2) {
    int len = min(s1.length(), s2.length());
    int over_len = 0;
    for(int i = 1; i <= len; ++i){
        string f = s1.substr(s1.length() - i);
        string s = s2.substr(0, i);
        if(f == s)
            over_len = i;
    }
    return s1.length() + s2.length() - over_len;
}

int solution(string s1, string s2) {
    return min(overlap(s1, s2), overlap(s2, s1));
}​

 

---

문제6) 소수 구하는법 참고해 놓기

 

어떤 수를 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 구하려 합니다.

예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.

1. 3+7+23
2. 3+11+19
3. 3+13+17
4. 5+11+17

자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 return 하도록 solution 함수를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

※ 1,000 이하인 소수는 168개 있습니다.

매개변수 설명

n이 solution 함수의 매개변수로 주어집니다.

* n은 1,000 이하인 자연수입니다.

return 값 설명

n을 서로 다른 소수 3개의 합으로 표현하는 방법의 수를 return 해주세요.
* 만약, n을 서로 다른 소수 3개의 합으로 표현할 수 없다면 0을 return  해주세요.

---

int solution(int n) {
    int answer = 0;
    vector<int> primes = {2};
    for (int i = 3; i <= n; i += 2) {
        bool is_prime = true;
        for (int j = 2; j < i; j++) 
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        if (is_prime)
            primes.push_back(i);
    }
    int prime_len = primes.size();
    for (int i = 0; i < prime_len - 2; i++)
        for (int j = i + 1; j < prime_len - 1; j++)
            for (int k = j + 1; k < prime_len; k++)
                if (primes[i] + primes[j] + primes[k] == n)
                    answer++;
    return answer;
}