[COS Pro] 1급 2차 C++ (조합)

 (어제 못 푼 2차 48분 걸렸다.

---

문제4)

자연수가 중복 없이 들어있는 배열이 있습니다. 이 배열에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법은 몇 가지인지 세려고 합니다.

자연수가 들어있는 배열 arr가 매개변수로 주어질 때, 이 배열에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법의 가짓수를 return 하도록 solution 함수를 완성해주세요.

매개변수 설명
자연수가 들어있는 배열 arr가 solution 함수의 매개변수로 주어집니다.
* arr의 길이는 3 이상 100 이하입니다.
* arr에는 1 이상 1,000 이하의 자연수가 중복 없이 들어있습니다.
* K는 1 이상 10 이하의 자연수입니다.

return 값 설명
배열에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법의 가짓수를 return 해주세요.
* 그러한 방법이 없다면 0을 return 하면 됩니다.

 

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> arr, int K) {
    vector<int> v(arr.size(),0);
	v[arr.size()-1] = 1, v[arr.size()-2] = 1, v[arr.size()-3] = 1;
	
    int answer = 0;
		do {
			int sum = 0;
			for(int i=0; i<arr.size(); i++) {
				if(v[i] == 1) sum += arr[i];
			}
			if(!(sum % K))answer++;
			
		}while(next_permutation(v.begin(), v.end()));
	
    return answer;
}

---

정답지

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> arr, int K) {
    int n = arr.size();
    int count = 0;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            for(int k = j + 1; k < n; ++k)
                if((arr[i]+arr[j]+arr[k])%K == 0)
                    count += 1;
    return count;
}

 

---

문제5)

자연수가 들어있는 배열이 있습니다. 이 배열에서, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 구하려 합니다. 단, 바로 전 숫자와 현재 숫자가 같은 경우는 증가한 것으로 보지 않습니다.

예를 들어 배열에 순서대로 [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]가 들어있는 경우, [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가한 가장 긴 구간이며, 길이는 4입니다.

자연수가 들어있는 배열 arr가 매개변수로 주어질 때, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 하도록 solution 함수를 완성해주세요.

매개변수 설명
자연수가 들어있는 배열 arr가 solution 함수의 매개변수로 주어집니다.
* arr의 길이는 2 이상 200,000 이하입니다.
* arr의 원소는 1 이상 1,000,000 이하의 자연수입니다.

return 값 설명
숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 해주세요.
* 길이가 2 이상인 증가하는 구간이 없다면 1을 return 해주세요.

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> arr) {
    int answer = 1;
		int len = 1;
		for(int i=1; i<arr.size(); i++)	{
			if(arr[i]>arr[i-1]){
				len ++;
			}else {
				answer = max(answer,len);
				len = 1;
			}
		}
    return answer;
}

---

정답)

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> arr) {
    int arr_len = arr.size();
    vector<int> dp(arr_len, 1);
    for(int i = 1; i < arr_len; ++i)
        if(arr[i] > arr[i-1])
            dp[i] = dp[i-1] + 1;
    int answer = 0;
    for(int i = 0; i < arr_len; ++i)
        answer = answer < dp[i] ? dp[i] : answer;
    return answer;
}