알고리즘 썸네일형 리스트형 1005번 1005번 - ACM Craft 다익스트라 알고리즘을 이용해서 문제를 풀 수 있었다. 위상정렬을 이용해서도 풀 수 있을 것 같다. (위상정렬 기억이 흐릿해서 인지 다익스트라가 끌렸다. -> 위상정렬 다시 공부) 결국 맨마지막 목적지에서 다른 목적지까지 거리를 모두 구하고, 그 거리의 최대값을 출력하면 된다(단, 가지 못하는 곳 제외) 만약 건물 X->Y라고 한다면 나는 간선을 Y->X로 주었다. 그리고 주어진 시간 값들을 우선 음수로 변경해서, 다익스트라 알고리즘을 사용했다. 그렇게 되면 최단 거리를 구하는 다익스트라 알고리즘에서 최대값을 구할 수 있게 된다. 최대값을 구하는 이유는 시간은 결국 큰 값에 의해서 좌우되기 때문이다. 12345678910111213141516171819202122232425.. 더보기 1004번 1004번 - 어린 왕자 주어진 점이 원 안에 존재하는지를 따지면 된다. 즉 각 점과 모든 원들의 중심과의 거리를 구하고, 구한 값을 반지름과 비교한다. 반지름보다 작다면 원안에 존재한다는 것이고, 반지름보다 크다면 원 밖에 존재하는 것이다. 원 밖에 존재하면 겹치는 원은 없다고 문제에 나오기 때문에 어떤 방식으로든 피해서 목적지에 도달 할 수 있다. 따라서 원 안에 존재하게 될때 진입/이탈이 이루어지는데 그 갯수를 세주면 된다. 단 한 원안에 출발점과 목적점이 둘다 존재한다면, 그 값은 카운트 하지 않는다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include#includeusi.. 더보기 1002번 1002번 - 터렛 처음에는 범위안의 모든 값을 구하는 건줄 알았는데 문제를 잘 읽어보니, 반지름과 중심을 이용한 수학문제였다.. 중심이 겹칠때, 중심이 겹치지 않을 때 나누면 겹칠때 - 반지름의 합이 중심거리와 같으면 무한대, 아니면 0 안 겹칠 때 - 0개인 경우 -> 아주 멀리 떨어져 있거나, 아주 큰 원이 작은 원을 품고 있거나 - 1개인 경우 -> 중심의 거리와 반지름의 거리가 같을 때, 혹은 아주 큰 원과 작은 원이 내접해서 한점 - 2개인 경우 -> 그 외 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include#includeusing namespace std;.. 더보기 1874번 1874번 - 스택 수열 스택을 k로 표현하고, 수열을 order 배열에 집어넣어서 시뮬레이션 처럼 맞췄다. order 배열의 해당하는 i 번 인덱스와 비교해서 작으면 k 값을 push 시켜서 맞추고 pop 시킨다. push , pop 을 할 때에는 이미 써버린 숫자면 그냥 지나치도록 k++ 나 k-- 를 해준다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include#include#includeusing namespace std;int order[100001];bool num[100001];int n, k;vector.. 더보기 4050. 재관이의 대량 할인 4050. 재관이의 대량 할인 할인을 최대한 받기 위해서는 큰 값들을 할인 받아야 한다. 따라서 나는 가격을 정렬하고, 리버스 해서 가장 큰 값부터 3개씩 묶어나가는 방법으로 문제를 풀었다. 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#includeusing namespace std; int c[100001];int n, ans;void init(){ ans = 0; memset(c, 0, sizeof(c));}int main(){ int tc; cin >> tc; for (int t = 1; t > n; init(); for (int i = 0; i > c[i]; } sort(c, c + n.. 더보기 4053. 전국민 건강 프로젝트 4053. 전국민 건강 프로젝트 시뮬레이션 문제 같은데 푸는데 꽤나 시간이 걸렸다.. 문제의 조건을 보니 시간초과를 해결하는게 가장 중요해 보였다. 맨 처음에는 -> 와 > tc; for (int t = 1; t > N >> T >> Q; for (int i = 0; i > per[i].p >> per[i].d; if (per[i].d == 2) { per[i].d = -1; } } // -> = p2) { if (i - 1 >= 0) { q.push(i - 1); } if (i + 1 = 0) { q.push(i - 1); } if (i + 1 더보기 1072번 1072번 - 게임 처음 문제 봤을 때는 막 완전탐색으로 문제를 풀려고 했는데, 값이 크다보니 시간초과가 많이 걸렸던 걸로 기억한다. 다시 문제를 보니 그냥 수학적인 식으로 풀 수 있을 것 같았다. 즉, k를 이긴 횟수라고 하면 ((Y+k)/(X+k))*100 은 k번 이겼을 때 승률이라고 할 수 있다. 그런데 이 값이 기존의 Z와 달라지려면, Z+1 보다 크거나 같을 때 k 값을 구하면 된다. ((Y+k)/(X+k))*100 >= Z+1 이라고 놓고 푼다면, k값의 범위를 알 수 있게 된다. 단 승률이 100이면 더 이상 오를수가 없고, 저걸 식으로 구하면 Z가 99면 분모가 0이 되므로 값을 구할 수 없다. 따라서 Z가 99보다 크거나 같을 때와, 그렇지 않은 부분으로 구해야한다. 1234567891.. 더보기 10219번 10219번 - Meats On The Grill 아무리 생각해도 어떻게 풀어야할지 감이 안잡혔다.. 엄청 어려운거 같은데 왜 정답률이 이렇게 높을까...하면서 결국은 다른 사람들꺼를 봤다.. 그냥 전체 Grill 을 뒤집으면 되는 방법이었다. 문제를 너무 어렵게만 풀려고 하는 것 같다, 이런 획기적인 방법을 떠올리는게 더 중요한데 123456789101112131415161718192021222324252627282930313233343536#include#include using namespace std;int h, w;char map[12][12];int main(){ int tc; cin >> tc; for (int t = 1; t > h >> w; for (int i = 0; i map[i][j.. 더보기 이전 1 ··· 8 9 10 11 12 13 14 ··· 46 다음 목록 더보기