11501 주식
이넘에,,코드는...맞는데 왜 자꾸 틀리대...ㅋ
그리디로 풀었다. 현재 남은 날짜 중 가장 주가가 높은 날 주식을 팔고 나머지 경우에는 주식을 한주씩 산다. 주가가 가장 높은 날 보유한 주식이 0이라면 아무것도 하지 않는다.
-
주가가 내림차순인 날에 정답이 음수로 뜨는 오류가 있었다. max_element를 처음 사용해보는데 v.begin()+i 로 식을 써서 생긴 문제...였다. max인 날에 도착하면 다음 max를 찾아야 하는데 v.begint()+i+1이 바른 식이었다. 다른 블로그들을 너무 믿으면 안되겠다. 역시 인생은 실전^^
-
첫 제출 때 틀렸습니다가 떴다. 최대 1000000*10000이면 당연히 21억 넘어가는데 int로 출력해서 생긴 오류였다. long long으로 바꾸는 것으로 해결했다.
처음부터 범위가 커서 int형에 걸릴거라는 불안함이 있었는데 진짜 걸렸다. 1000000*10000이므로 21억 넘어가니까 그냥 사용한 변수들 다 long long처리해버렸다. current만 처리해도 됐을거같다. 여러 반례 처리하니까 식 자체는 맞는거같은데 범위가 커질수록 시간이 너무 오래걸려서 시간초과 뜬다. 반복문 몇개 손봐야될 것 같다.
복잡도 문제가 제일 중요한건 알지만 제일 귀찮고 어렵다.
<추가>
알고리즘 헤더에 있는 max_element함수 복잡도가 o(n)이라고 한다. 안그래도 이중반복문인데 이런 함수를 써서 시간초과가 나왔다고 판단하고 알고리즘을 전면 수정했다. 마지막 날의 주가를 최고 주가로 설정해놓고 뒤에서 앞으로 돌면서 그것보다 주가가 큰 날을 만났을 때 최대 주가를 수정하고 최대주가 - 현재 주가를 더해주는 방식이다. 이러면 최대주가==현재주가일 때 아무것도 안한 것과 같은 효과가 있다. 개짱천재적인 코드다. 세상에 이렇게 똑똑한 사람들이 많다니 신기하다.
이 알고리즘은 블로그 뒤져보다가 알게됐다. 스스로 생각해낸 방법이 아니기 때문에 문제에 진 기분이 든다. 그러나 코드도 간결해지고 복잡도 문제도 해결됐다. 오늘도 이렇게 시야를 넓혀간다.
[수정 전 코드]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
long long n, l, max, cnt, current;
vector<int>v;
cin >> n;
for (int j = 0; j < n; j++)
{
v.clear();
int m;
cnt = current = 0;
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> l;
v.push_back(l);
}
max = *max_element(v.begin(), v.end());
for (int i = 0; i < m; i++)
{
if (v[i] == max)
{
if (cnt != 0)
{
current = (cnt * v[i]) + current;
cnt = 0;
if (i != m - 1)
max = *max_element(v.begin() + i + 1, v.end());
}
else
{
if (i != m - 1)
max = *max_element(v.begin() + i + 1, v.end());
continue;
}
}
else
{
current = current - v[i];
cnt++;
}
}
cout << current << '\n';
}
return 0;
}[수정후]
#include <iostream>
#include <vector>
using namespace std;
int main()
{
long long int T, N, current, max;
vector<int>v;
cin >> T;
while (T--)
{
cin >> N;
current = 0;
for (int i = 0; i < N; i++)
{
int n;
cin >> n;
v.push_back(n);
}
max = -1;
for (int i = N - 1; i >= 0; i--)
{
if (max < v[i])
max = v[i];
current += max - v[i];
}
v.clear();
cout << current << '\n';
}
return 0;
}11650 좌표 정렬하기
pair쓰면 쉽게 풀릴거같이 생겨서 그렇게 풀었는데 실제로도 쉽게 풀렸다. 그런데 풀고나서 찝찝해서 다른 사람들 코드를 찾아보니 compare함수 커스텀에 초점이 맞춰진 문제였던듯하다. 나도 sort함수 쓰긴 했는데 인자 두개만 씀 ㅎㅎ;
다른것보다 compare함수 만들 때의 작동원리를 알아야될 것 같아서 적어본다. 보통 수식이나 bool타입 함수로 만드는데 true면 sort고 false면 무시다. 이걸로 오름차순, 내림차순도 정할 수 있고 조건 걸어서 원하는 방식으로 정렬할수도 있다. c++로 문제풀면 몇번 보게 될 코드같아서 미리 학습해둔다.
물론 지금 코드에는 안 썼다ㅎ
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int N,a,b;
cin >> N;
vector<pair<int, int>>v;
for (int i = 0; i < N; i++)
{
cin >> a >> b;
v.push_back(pair<int, int>(a, b));
}
sort(v.begin(), v.end());
for (int i = 0; i < N; i++)
{
cout << v[i].first << " " << v[i].second << "\n";
}
return 0;
}11651 좌표 정렬하기 2
바로 다음 문제가 똑같은건지 몰랐다고요~~~ 이건 인자 두개로 해결이 안돼서 위에서 말한 커스텀 컴페어 해봤다. 블로그 찾아보다가 클래스 보고 솔깃해서 pair대신 클래스 만들어줬다.
compare만들면서 의아했던건 왜 매개변수를 레퍼런스로 받지...? 였는데 확인해보니 굳이 레퍼런스로 안 받아도 된다. 그냥 값에 의한 전달로도 리턴은 0 아니면 1이니까 이건 상관없었다. 기억하자! true일 때 정렬! false일 때 무시!
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class a {
public:
int x;
int y;
a(int ax,int ay) {
x = ax;
y = ay;
}
};
bool new_sort(a &x, a &y)
{
if (x.y < y.y)
return true;
else if (x.y == y.y)
{
if (x.x < y.x)
return true;
else
return false;
}
else
return false;
}
int main()
{
int n, x, y;
vector<a> v;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
v.push_back(a(x,y));
}
sort(v.begin(), v.end(),new_sort);
for (int i = 0; i < n; i++)
{
cout << v[i].x << " " << v[i].y << "\n";
}
return 0;
}