iridescent

https://www.acmicpc.net/problem/2217

이 친구는 좀 쉬웠는데,,
왜 안 됐을까 아직도 모르겠다.

나는 정렬하기 귀찮아서 set을 썼었는데,,
틀렸다,,
set이랑 배열이랑 무슨 상관일까?
포인터로 접근해서 그런가,,,,,,,,

set 말고 배열로 할당받아 계산하니 됐다.

이 알고리즘은 엄청 간단하다.

• 정렬한다.
• 정렬한 첫번째 값(젤 작은 값 ) * testcase랑 곱한다.
• testcase는 감소하면서 두 번째 값을 곱한다.
• 젤 큰 값을 찾는다.

이렇게 하는 이유가,
로프는 전체를 쓸 필요가 없고, 들어올릴 수 있는 최대 중량을 구하는 것이다.

생각해보면 간단하다.
예를 들어
40
100
2
5000
무게를 들 수 있는 로프가 있다.

정렬을 안 해보고 생각해보자
40 부터 1개니깐, 무게는 40
40,100 개를 들면, x/2 = 40(최소 40들 수 있음) → 최대 80
40, 100, 2이면 : x/3 = 2(최소 2 들 수 있음) → 최대 6
40, 100, 2, 5000 : x/4 = 2(최소 2 들 수 있음) → 최대 8

여기서 젤 큰 값은 80이다.
따라서 최댓값은 80이다.
로프를 전부 포함 안 해도 된다고 했으니
이런 결과값이 나올 수 있다.

#include<iostream> #include <set> #include <algorithm> using namespace std; int main() { int input[100001]; int testcase; cin >> testcase; long long max_num = 0; for (int i = 0,num; i < testcase; i++) { cin >> num; input[i] = num; } sort(input, input + testcase); for (int i = 0,mul = testcase; i < testcase; i++) { long long cal_num = (mul--) * input[i]; if(max_num < cal_num) max_num = cal_num; } cout << max_num; return 0; }

https://www.acmicpc.net/problem/1343

이건 그냥 음 처음에는 split써서 . 나눌까 했는데
그럼 ...이 여러개 나오면?
결국 구현했긴 한데
틀렸다.

그래서 순서대로 구해보기로 했는데

알고리즘은 간단하다.
1. 입력받는다.
2. "."과 문장 끝이 아니면 카운트센다
3. "."이 나오거나 문장끝이면

• 카운트가 홀수이면 구현할 수 없기 때문에 "-1" 출력
• 4로 나눠지면 "AAAA"추가
• 2로 나눠지면 "BB"추가

#include <iostream> #include <string> using namespace std; int main() { string input_str; cin >> input_str; string output; int count = 0; for (int i = 0; i < input_str.size()+1; i++) { if (input_str[i] == '.' || input_str[i] == '\0') { if (count % 2 != 0) { cout << "-1"; return 0; } while (count / 4 != 0) { output+= "AAAA"; count -= 4; } while (count / 2 != 0) { output += "BB"; count -= 2; } if (i != input_str.size()){ output+="."; count = 0; } } else { count++; } } for (int i = 0; i < output.size(); i++) { cout << output[i]; } return 0; }

python

#1343 import sys input_str= str(input()) count = 0 output = "" for i in range(len(input_str)+1): if i == len(input_str) or input_str[i] == '.' : if count % 2 != 0: print("-1") sys.exit() while(count //4 != 0): output += "AAAA" count -= 4 while (count//2 != 0): output += "BB" count -= 2 if i != len(input_str): output += "." count = 0 else: count+=1 print(output) 

https://www.acmicpc.net/problem/14916

이 문제는 한번 생각을 해보아야 한다.
무조건 5를 나누는게 아닌, 최소한의 개수를 구해야한다.
그래서 나는 처음에 1부터 계산 해보았다.

이렇게 보면,
5의 배수는 무조건 5원으로 나눈다.
그런데 2원은 무조건 2로 나눠진다고 해서 바뀌는게 아니였다.

생각해보면 쉽다.
5원까지는 미리 적어놔야하거나,
아니면 계산하면된다. -1이 있으니
5원부터는 앞에꺼 들고오는 식이다.

1. 또 여기서 10원 이하는 2의 몫이다.
2. 10이하의 홀수들은 배열[i-5]의 값에 +1을 하면된다.
왜냐면 5원을 빼면 2원이 남거든.
남은 걸 계산하지말고 들고오자!

이런것이다.
c++코드는 좀 오래전에 짜서

#include <iostream> using namespace std; int main() { int check[100001] = { -1,-1,1,-1,2, }; int num; int count = 0; cin >> num; for (int i = 5; i <= num; i++) { if (!check[i]) { if (i % 5 == 0) { check[i] = i / 5; } else { if (check[i - 5] == -1)check[i] = i / 2; else { check[i] = check[i-5] + 1; } } } } cout << check[num]; return 0; }

python

input_num = int(input()) check = [] for i in range(1,input_num+1): if (i%2 != 0) &(i %5 != 0) and i < 5: check.append(-1) else: if (i % 5 == 0): check.append(i//5) elif (i <10 and i % 2 == 0): check.append(i//2) else : check.append(check[i-6] + 1) print(check[input_num-1]) 

python 더 열심히 해보자.

https://www.acmicpc.net/problem/5585

그냥 어 

읽고 바로 생각했다.

시간 적기로 했는데.

알고리즘 

• 500부터 나눠서 나눈 몫을 더하고
• 나눈 나머지를 가지고 또 500확인한다. 
• 500이 확인 다 했으면 (500으로 나눈 몫이 0이면 )
• 그 다음 100으로 넘어간다. 

소스코드 

#include <iostream>

using namespace std;
int main() {
	int input,output = 0;
	int coin[6] = { 500,100,50,10,5,1 };
	cin >> input;
	input = 1000 - input;
	for (int i = 0; i < 6; i++) {
		while (input / coin[i] != 0) {
			output += input / coin[i];
			input %= coin[i];
		}
	}
	cout << output;
	return 0;
}

python

coin = [500,100,50,10,5,1]
input_num = int(input())
output = 0
input_num = 1000-input_num
for i in range(6):
    while (input_num//coin[i]) != 0:
        output += input_num//coin[i]
        input_num %= coin[i]
        
print(output)

https://programmers.co.kr/learn/courses/30/lessons/12977

계속 소수인지 확인하니깐

"에라토스테네스의 체"를 썼다. 

에라토스테네스의 체의 알고리즘은 내가 이해하기론 위키백과가 제일 좋은 것 같다. 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

간단하게 생각하면 

2의 배수 빼고, 3의 배수 빼고, 5의 배수 빼고, 다 빼면,,,

소수가 남아있는다. 

나는 프로그래머스를 오랜만에 해서 오류가 났는데 

오류가 Aborted (core dumped 에러) 가 났다. 

내 생각엔 check배열의 크기가 문제였다. ㅋㅎㅋㅎ...

세상에,,,

그래도 해결했당 ㅎㅎㅎㅎ

너무 신낭

<알고리즘>

에라토스테네스의 체를 사용해서 소수를 구한 뒤

3개의 숫자를 받아 숫자를 만든다(num)

확인한다. 

엉청 간단한데, 

에라토스테네스의 체가 문제가 아닌

나는 3개의 숫자를 받아서 숫자를 만들때, 

bfs를 사용해서,,

더 별로 였다,,

글너데 이런 방법을 사용하니 간단했다. 

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int max_num = 0;

int solution(vector<int> nums) {
	int answer = 0;
	int check[1001] = { -1,-1,0,0,-1};
	for (int i = 2; i <= sqrt(1001); i++) {
		if (!check[i]) {
			for (int j = 2; i*j <= 1001; j++)
				check[i*j] = 1;
		}
	}
	for (int i = 0; i < nums.size(); i++) {
		for (int j = i + 1; j < nums.size(); j++) {
			for (int k = j + 1; k < nums.size(); k++) {
				int num = nums.at(i) + nums.at(j) + nums.at(k);
				if (check[num] ==0)
					answer++;
			}
		}
	}
	return answer;
}
int main() {
	vector<int> num = {1,2,7,6,4};
	
	cout << solution(num);
}

이 코드는 비쥬얼에서 한번 실행해본다고,ㅎㅎㅎ

main까지 있는 것이다. ㅎㅎ

https://www.acmicpc.net/problem/11399

최솟값을 구하라고 했으니,

처음부터 많은 것을 더하는 것 보단

작은걸 계속 더하는게 좋으니

정렬해서 더하면 되겠다 생각했다. 

1. 입력받고

2. 정렬하고

3. 각 순서마다 값을 더한다.

4. 3번에서 더한 값을 계속 더한다. 

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


int main() {

	int testcase,output = 0;
	cin >> testcase;
	multiset<int> input;
	for (int i = 0,num; i < testcase; i++) {
		cin >> num;
		input.insert(num);
	}
	int sum = 0;
	for (multiset<int>::iterator it = input.begin(); it != input.end(); it++) {
		sum += *it;
		output += sum;
	}
	cout << output;
	return 0;
}

python 공부를 해보자해서 하려는데

python 문법 공부 제대로 안 해봐서 생소했다. 

testcase = int(input())
a = list(map(int,input().split()))
a.sort()
sum = 0
output = 0
for i in a:
    sum += i
    output += sum
print(output)

list(map(int, input().split())))

생각하자. ㅎㅎㅎ

이것 때문에 int형 안 더했다고,, 오류났었따,,

https://www.acmicpc.net/problem/9237

일단 첫 번째 시도를 실패했는데 

문제를 잘못 읽었다.

나무 심는 순서를 신중하게 골라서 최대한 빨리 초대하려고 한다

심는 순서를 내가 정하는 것이었다!!!

차례대로인 줄

문제를 잘 읽자.

먼저, 최대한 빨리 초대하려고 하니깐,

정렬을 했다.

정렬하고 나서 묘묙 하나를 심는데 걸리는 시간이 1일 걸린다고 했다.

그러니 심는데 시간이 1일이 걸린다고 먼저 더하고 시작해야 하는 것이다. 

정리해보자면, 

만약 묘목 자라는데 걸리는 시간이 5 9 8 2라고 하자.

정렬하면

2 5 8 9이다. 

그럼 빨리 초대하려고 하니깐. 

그럼 묘목 자라는데 걸리는 시간이 9일 걸리는 묘목부터 심어야 한다.

그런데 묘목 심는데 걸리는 시간이 1일이니깐,

9일 걸리는 묘목을 심는 데는 1+9일이 걸리고 

이장님을 초대하는데 다음날 초대하니깐 

결과는 9 +2일이 걸리는 것이다.

이렇게 더하면

2 5 8 9 묘목은

+ 5 4 3 2

 7 9 11 11일 걸린다. 

그럼 최댓값은 11일.

최대 11일이 걸린다. 

소스코드는 

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


int main() {
	int count;
	int max_num = 0;
	int input[100001];
	cin >> count;

	for (int i = 0,num; i < count; i++) {
		cin >> input[i];
	}
	sort(input, input + count);

	for (int i = count - 1,add =2; i >= 0; i--) {
		max_num = max(input[i] + add, max_num);
		add++;
	}
	cout << max_num;
	return 0;
}

www.acmicpc.net/problem/2304

이건 알고리즘 공부하기 전에 말도 안 되게 짰다가

틀려서 다시 오랜만에 시도한 문제이다.

c++ 중에 map이라는 걸 사용할 것이다.

map은 key값과 value가 한 쌍으로 되어있는 컨테이너이다.

알고리즘
1. map에 넣는다 (위치, 높이)
   1-1). map에 넣으면서 높이가 젤 큰 값을 구한다. (위치도 젤 큰 값)
   1-2). map에 넣으면서 마지막 위치를 구한다.

2. iterater를 이용하여 map의 젤 앞의 위치와 높이를 저장하고 iter를 map의 두 번째 위치로 바꾼다.

3. iter를 1-1)에서 구한 젤 큰 위치 값까지 for을 돌린다.
   3-1). 앞의 높이가 현재 가리키고 있는 iter의 높이보다 작거나 같으면
          사각형의 넓이를 더해준다.
          앞의 위치를 현재 위치, 앞의 높이를 현재 높이로 대입한다.

4. 젤 큰 값은 앞의 for문으로 돌리지 않았기 때문에 높이만 더해준다(넓이가 1이라서)

5. iter를 lower_bound를 이용하여 1-2)에서 구한 마지막 위치로 가리킨다.

6. iter를 이용하여 젤 뒤의 위치와 높이를 저장하고 iter를 map의 뒤에서 두번째 위치로 바꾼다.

7. iter를 1-1)에서 구한 젤 큰 위치 값까지 for문 돌린다.
   7-1). 뒤의 높이가 현재 가리키고 있는 iter의 높이보다 작으면 
          사각형의 넓이를 더해준다.
          뒤의 위치를 현재위치, 뒤의 높이를 현재 높이로 대입한다.

8. 넓이를 출력

위 그림식으로 끝에서 젤 큰 높이를 향하여 더해준다.

이 문제에서의 반례는

이러한 상황이다. 최대의 높이가 두개 이상일 경우,

이 반례를 생각하지 않는다면 최대 높이만 구하여한다면 틀린다. 

나도 그렇게 틀렸었다.

소스 코드

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

int main() {
	map<int, int> m;
	int testcase;
	int row, hight;
	int max_row = 0, max_hight = 0;
	int sum = 0;
	int last_row = 0;
	cin >> testcase;
	while (testcase--) {
		cin >> row >> hight;
		m.insert(pair<int, int>(row, hight));
		if (max_hight <= hight) {
			max_hight = hight;
			max_row = row;
		}
		if (last_row < row) {
			last_row = row;
		}
	}

	map<int, int>::iterator iter;
	iter = m.begin();
	int my_row = iter->first;
	int my_hight = iter->second;
	iter++;
	for (; my_row != max_row; iter++) {
		if (my_hight <= iter->second) {
			sum += (iter->first - my_row) * my_hight;
			my_row = iter->first;
			my_hight = iter->second;
		}
		
	}
	sum += my_hight;
	
	iter = m.lower_bound(last_row);

	my_row = iter->first;
	my_hight = iter->second;
	iter--;
	for (; my_row != max_row; iter--) {
		if (my_hight <= iter->second) {
			sum += (my_row - iter->first) * my_hight;
			my_row = iter->first;
			my_hight = iter->second;
		}
	}
	cout << sum;
	return 0;
}