[ 이코테 2. Greedy ]

< 본 게시글은 유튜버 [ 동빈나 ] 님의 유튜브 영상과 git hub 교재 를 공부하고 정리한 글 입니다. >

 

[ Greedy ]

[#1 1이 될 때까지] / [#2 곱하기 혹은 더하기- Face book 인터뷰 기출] / [#3 모험가 길드- 핵심 유형]

---------------------------------------------------------------------------------------------------------------------------------

 

#1 1이 될 때까지

---

[ 내 풀이 ]

 

#include<iostream>

using namespace std;

int n, k;
int rest;
int cnt;

int main() {
	cin >> n >> k;
	while (n != 1&&n>=k) {
		rest = n % k;
		cnt += rest;
		n = n - rest;
		n = n / k;
		cnt++;
	}
	if (n < k) {
		while (n != 1) {
			n--;
			cnt++;
		}
	}
	cout << cnt;

	return 0;
}

 

[ 정답 ]

#include <bits/stdc++.h>

using namespace std;

int n, k;
int result;

int main() {
    // N, K를 공백을 기준으로 구분하여 입력 받기
    cin >> n >> k;

    while (true) {
        // N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
        int target = (n / k) * k;
        result += (n - target);
        n = target;
        // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
        if (n < k) break;
        // K로 나누기
        result += 1;
        n /= k;
    }

    // 마지막으로 남은 수에 대하여 1씩 빼기
    result += (n - 1);
    cout << result << '\n';
}

 

복습하면서 다시 푼 코드인데 아래의 코드도 정답인것 같다.

	int cnt = 0;
	cin >> N >> K;
	while (N != 1) {
		if (N%K == 0) {
			N /= K;
			cnt++;
		}
		else {
			N -= 1;
			cnt++;
		}
	}
	cout << cnt;

---

배운 점 :

 

 int target = (n / k) * k ;

n 이 k 에 나누어 떨어지지 않더라도 나누어 떨어지는 가장 가까운 수를 찾을 수 있다.

 

 if( n  < k) break

이런 나누기 문제일땐 항상 n이 k 보다 작을 경우를 생각해줘야한다. 안그러면 while 문에서 무한 루프에 빠진다.

 

result += (n - 1); // 마지막으로 남은 수에 대하여 1씩 빼기

while (n != 1) {
		n--;
		cnt++;
	}

내가 쓴 코드를 그냥 cnt += ( n-1 ) ; 한줄로 처리 할 수 있었다.

 

---

#2 곱하기 혹은 더하기

 

 

 

우선 처음에 DP로 풀어보려고 DP[X] 는 X를 가지고 만들 수 있는 가장 큰 수라고 정의했다.

그러고 보니 X에 올 수 있는 수의 자리수가 최대 20 자리이기 때문에 long long도 부족하다는것을 알고 그리디로 풀어야겠다 하고 생각 할 수 있었다.

 

[ 내 풀이 ]

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


using std::cout; using std::cin;
using std::vector;

std::string S;


int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	vector<int> input;
	cin >> S;
	for (int i = 0; i < S.length(); i++) {
		input.push_back(S[i] - '0');
	}
	int result=0;
	for (auto itr = input.begin(); itr != input.end(); itr++) {
		if (result == 0) {
			result += *itr;
		}
		else {
			if (*itr == 1 || *itr == 0) {
				result += *itr;
			}
			else {
				result *= *itr;
			}
		}
	}
	cout << result;

	return 0;
}

 

[ 정답 ]

#include <bits/stdc++.h>

using namespace std;

string str;

int main(void) {
    cin >> str;

    // 첫 번째 문자를 숫자로 변경한 값을 대입
    long long result = str[0] - '0';

    for (int i = 1; i < str.size(); i++) {
        // 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
        int num = str[i] - '0';
        if (num <= 1 || result <= 1) {
            result += num;
        }
        else {
            result *= num;
        }
    }

    cout << result << '\n';
}

 

---

배운 점 :

 

- 그냥 두 수 중에서 하나라도 '0' 혹은 '1' 인 경우를 생각하면 되는데..

나는 지엽적으로 s[i]의 값만 가지고 0 이나 1이면 어떻게 해야지 하고 생각했다. 그래서 코드가 쓸데없이 길어졌다.

for (auto itr = input.begin(); itr != input.end(); itr++) {
		if (result == 0) {
			result += *itr;
		}
		else {
			if (*itr == 1 || *itr == 0) {
				result += *itr;
			}
			else {
				result *= *itr;
			}
		}
	}

 

---

#3 모험가 길드

 

 

 

 

 

 

[ 내 풀이 ] - 실패

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


using namespace std;

int answer;
int n, x;
vector<int> traveler;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	traveler.reserve(n);
	for (int i = 0; i < n; i++) {
		cin >> x;
		traveler.push_back(x);
	}
	sort(traveler.begin(), traveler.end());

	
	int max=0;
	while (max <= traveler.size()) {
		auto itr = traveler.begin();
		max = *itr;
		int i = 0;
		for (i; i < max; i++) {
			if (traveler[i] > max) { 
				max = traveler[i];
				break;
			}
		}
		
		traveler.erase(itr, itr + i);
	}


	

	return 0;
}

 

[ 정답 ]

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    sort(arr.begin(), arr.end());

    int result = 0; // 총 그룹의 수
    int count = 0; // 현재 그룹에 포함된 모험가의 수
    int p = 0;
    for (int i = 0; i < n; i++) { // 공포도를 낮은 것부터 하나씩 확인하며
        p = arr[i]; // 현재 그룹의 공포도
        count += 1; // 현재 그룹에 해당 모험가를 포함시키기
        if (count >= p) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
            result += 1; // 총 그룹의 수 증가시키기
            count = 0; // 현재 그룹에 포함된 모험가의 수 초기화
        }
    }

    cout << result << '\n'; // 총 그룹의 수 출력
}

 

---

배운 점 :

 

- 문제를 너무 어렵게 접근하려고 했었다.

( 매번 이렇게 공식이 없는 문제를 풀때마다 이상한 길로 새는거 같다. )

먼저 문제 접근 방법부터 곰곰히 생각해보고 방향성이 잡혔을때 문제풀이를 시작해야겠다.

 

- reserve 해야되는걸 resize 해서 의도치 않게 원소 0이 traveler에 들어있었다. ( 조심하자 )

traveler.resize(n);