Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/11652 처음에 이 문제를 봤을 때는 받는 숫자와 그 수가 나온 횟수를 함께 저장한 후 계속 검사를 하면서 만약 새로운 수가 들어왔을 때 vector안에 그 숫자가 이미 있는지를 확인하고 만약 있다면 횟수를 늘리고 없다면 새로 vector안에 추가시켜주는 식으로 코드를 짜 보았다. #include #include #include using namespace std; struct Card { long long number; long long count; }; bool cmp(const Card &a, const Card &b) { if (a.count > b.count) return true; else if (a.count == b.c..

문제링크 : https://www.acmicpc.net/problem/10989 문제의 의도에 맞게 접근하지 않으면 메모리 에러로 틀리기 쉬운 문제이다. 이 문제의 핵심은 10000000개의 수를 sorting해도 제한된 메모리 안에서 처리를 하게 하는것이다. 고로 수를 받는대로 vector나 배열에 모두 집어넣고 sort를 시키면 안된다. 문제의 조건을 만족시키기 위해 가장 중요한점은 sorting할 숫자가 10000을 넘지 않는다는 것이다 그래서 나는 배열의 공간을 10000개를 주고 배열값을 0으로 설정한 후 들어오는 숫자에 해당하는 배열 값을 증가시키는 방법을 택하였다.(예를들어 num이라는 숫자가 들어오면 arr[num]++을 해준것이다.) #include #include using namesp..

문제링크 : https://www.acmicpc.net/problem/10814 #include #include #include #include using namespace std; struct Person { int age; //나이 string name; //이름 int number; //순서 }; bool cmp(const Person &x, const Person &y) { if (x.age < y.age) return true; //나이순으로 정렬 else if (x.age == y.age)//나이가 같다면 번호순으로 정렬 return x.number < y.number; else return false; } int main() { int number = 1; Person p; vector v;..

문제링크 : https://www.acmicpc.net/problem/2751 #include #include #include using namespace std; int main() { long long N, num; scanf("%lld", &N); vector v; while (N--) { scanf("%lld", &num); v.push_back(num); } sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) printf("%lld\n", v[i]); }

문제 링크 : https://www.acmicpc.net/problem/9461 정말 단순하게 규칙만 찾으면 풀 수 있는 문제이다. 길이가 memo배열에 할당시켰다고 했을 때 수를 쭉 나열해서 살펴보면 memo[i] = memo[i-1] + memo[i-5] 임을 알 수 있으며 이를 통해 memo[N]을 구하면 된다. #include #include #include using namespace std; long long memo[101]; int main() { memo[1] = 1; memo[2] = 1; memo[3] = 1; memo[4] = 2; memo[5] = 2; int T;int N; scanf("%d", &T); while (T--) { scanf("%d", &N); for (int i ..

문제링크 : https://www.acmicpc.net/problem/1699 #include #include #include #define SIZE 100001 using namespace std; int memo[SIZE]; int main() { long long N; scanf("%lld", &N); for (int i = 1; i

문제링크 : https://www.acmicpc.net/problem/2579 동적계획법으로 풀면 어렵지 않게 풀 수 있는 문제이다. 먼저 각 계단의 점수를 저장하기 위해 stair[301]을 선언하였고 계단을 올라갈 때 마다 최대 점수를 저장하기 위해 score[301][3]을 선언하였다. 여기서 score[i][0]은 그 전 계단을 밟고 i 번째 것을 안밟는 경우. score[i][1]은 그 전 계단을 밟지 않고 i번째 것을 밟는 경우. score[i][2]는 그 전 계단을 밟고 i번째 계단도 밟는 경우이다. #include #include using namespace std; long long score[301][3]; int stair[301]; int main() { int n; //계단의 수 ..

문제링크 : https://www.acmicpc.net/problem/1912 연속한 숫자중에 최대치를 구하는 문제이다. 처음으로 문제를 풀 때는 수열을 돌면서 음수가 나오면 그 전까지의 합계를 저장하고 만약 합계가 0보다 작을 떄는 합계를 다시 초기화하여 그 다음부터 다시 합계를 시작하고 저장하는 식으로 문제를 풀었다. #include #include #include #define SIZE 1000001 using namespace std; int arr[SIZE]; int main() { memset(arr, -1, sizeof(int)*SIZE); //모든 수를 -1로 초기화 long long n; scanf("%lld", &n); //받을 숫자의 갯수 for (int i = 1; i

문제링크 : https://www.acmicpc.net/problem/11054 #include #include #include using namespace std; int A[1001]; int B[1001]; int memo1[1001]; int memo2[1001]; int main() { int n; scanf("%d", &n); for (int i = 1; i A[j] && memo1[i] B[j] && memo2[i] < memo2[j] + 1) { memo2[i] = memo2[j] + 1; } } //기존의 LIS 방식으로 각 배열의 수 까지의 최대 수열의 길이 구하는 과정 if (memo2..

문제링크 : https://www.acmicpc.net/problem/11053 LIS알고리즘이 적용되는 과정에 대한 이해가 필요하다면 : http://dolphins-it.tistory.com/82 참조 #include #include #include #include using namespace std; int A[1001]; int memo[1001]; int main() { int n; scanf("%d", &n); for (int i = 1; i