알고리즘 스터디 1주차 그리디 알고리즘

오호라 greedy algorithm도 대충 스터디장님이 거스름돈 문제를 예시로 설명해주셨지만, 

나동빈님의 유튜브 영상을 보고 추가 공부를 했다. 

 

거스름돈 문제보고 완전 쉽네 이러고 회의배정 문제 풀었다가 2시간 고민하고 엉엉 울면서 다시 나동빈님 유튜브로 돌아옴,,,, 눈물 닦으면서 문제 같이 풀어보는 중,,,

 

# 1이 될 때까지 

거의 밥솥대가리를 부여잡고 엥 result 뭐야 이러고 있었는데 이해하고 감탄함 진짜 천재같아요 나동빈님

#include<iostream>
using namespace std;

int main() {
	int n, k; // 25 , 3
	cin >> n >> k;
	int count = 0;
	while (1) {
		if (n < k) break;
		int target = (n / k) * k; // target = (25/3)*3= 24
		count += (n - target); // count += 1  
        // 어차피 이만큼은 1로 빼야하기때문에 카운팅해야함
        n = target; // n = 24
        //1로 빼면 값이 바뀜 
		n /= k; // n = 24/3=8 
        //n이 k의 배수가 됐으므로 나눠줌
		count++; // 나눠주면 카운팅
	}
	count += (n - 1);
	cout << count << endl;
}

k로 n을 나눌 수 있으면 좋지만 사실 안 그런 경우가 더 많다. 

(n/k)*k 이라는 target을 구하면 n보다 작은 수 중에 n과 제일  가까운 k의 배수가 나온다.

그러면 우선 그 k가 될 때까지 n을 1씩 빼줘야하는데 여기서 감탄함 ㅠ

어차피 n - target 만큼 뺄 테니 이 숫자만큼을 counting 한다. 이후 n == target으로 만들어줌.

난 찌질하게 n --; count++; 이러고 있었는데 세상에나,,,,, 진짜 한 수 아니 두 수 배워감

그 후 k로 나눠주고 한 번 나눠줬으니까 1만큼 counting 함. 

반복하다보면 언젠가  n이 k보다 작아지는데 그러면 반복문을 탈출해서 우리의 목표는 1이 되는거므로 n-1만큼 또 counting을 해준다. 헐 재밌어

 

## 더하기 곱하기 

코드 스스로 생각해보고 짰는데 나동빈님이랑 비슷해서 기분 좋음 ㅎㅎ but 난 바보같이 int 로 짰지,,,

문제조건에 따르면 long long 이맞다.

#include<iostream>
#include<string>
using namespace std;

int main() {
	string s;
	cin >> s;
	int sum = s[0] - '0';
	for (int i = 1; i < s.size(); i++) {
		s[i] = s[i] - '0';
		if (s[i] <= 1 || sum <= 1) {
			sum += s[i];
		}
		else sum *= s[i];
	}
	cout<<sum;
}