오늘 여름학교에서 풀었던 문제 여름학교용 문제였기 때문에 범위가 훨씬 무자비해서 다 long long int로 선언해줬다 이거푸는데 몇시간 걸렸는데 그래도 플래를 처음으로 풀어낸거니 내 성장을 볼 수 있어 기뻤다. ​ https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있 www.acmicpc.net #include #include #include #define X first #define Y second #define MAX 9223372036..

랭작문제 정렬을 열심히 해주고 범위에 상관없이 가져갈수있는 책들 중 가장 앞번호만 가져가게 해주었다 모두가 앞번호를 가져가려 하고, 앞번호를 가져갈 수 있는 사람들부터 책을 나눠주게 되면, 가장 많은 수의 책을 나눠줄 수 있게 된다. ​ https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net #include #include #include #include using namespace std; bool chk[1010] = {0}; int n,m,a,b,c..

얘도 머 바로 전 글과 별반 다를게 없다. 설명은 바로전글 가서 들어도 될 거 같다. https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net #include #include #include #include using namespace std; struct POS{ int x; int y; };// 가입순서 - 나이 - 이름 vector v; bool compare(POS a, POS b){ if..

그냥 std 쓰자 편해서 좋았다. ​ https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net compare함수만 따로 잘 작성해주고 구조체 하나 짜주면 쉽게 풀 수 있다. #include #include #include #include using namespace std; struct JUDGE{ int priority; int age; char name[101]; };// 가입순서 - 나이 - 이름 vector v; bool compare(JUDGE a,..

간단한 유니온파인드 문제 유니온파인드에 관해서는 여름학교 수업 끝나고 정리하면서 글을 하나 작성할 계획이다. 이걸 보시는 분들은 아마 내 블로그에 유니온파인드 관련 글이 있을거다. ​ https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 유니온파인드는 간단히 말하자면 자신의 부모만을 기억하는 구조다 그래서 부모 노드가 자기 자신인 노드의 경우에는 자기자신이 하나의 루트노드가 되는 것이고, 두 집합끼리 합할 때..

처음으로 메모리 초과가 나온 문제. 이제부턴 메모리도 신경써서 풀어야겠다. ​ https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 배열을 maxdp를 50만정도, mindp를 50만, 입력도 50만으로 엄청많이 만들어서 메모리 초과가 나왔으나, 어디선가 들었던 기법을 통해 메모리를 대폭 절감해 통과할 수 있었던 문제이다. #include #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((..

2차원 배열에서의 Dp는 너무 어려운 거 같다 ㅠ 익숙해질때까지 많이 풀어봐야겠다.... ​ https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제 풀때에 있어 굉장히 어려운 부분이 한군데 있었다. ​ 5 5 10 25 7 8 13 68 24 -78 63 32 12 -69 100 -29 -25 -16 -22 -57 -33 99 7 -76 -11 77 15 ​ 테스트케이스에 입력이 이렇게 들어오는데 두번째 줄 첫번째 입력인 68의 경우 단..

무난한 dp 문제였다 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp문제를 쬐끔 풀어보면서 느낀게 있다면, 입력배열에서 모든걸 처리하려면 골치아프다는것이다. 그냥 dp배열 하나 더 만들자 ㅎㅎ #include int input[100001] = {0}; int dp[100001] = {0}; int max(int a, int b){ return a>b?a:b; } int main(){ int n,value = -1234; scanf("%d", &n)..

https://www.acmicpc.net/problem/2553 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net #include int f(int k, int t){ if(t == 1) return k; k = k*t; while(k%10 == 0) k/=10; k = k%100000; return f(k, t-1); } int main(){ int n; scanf("%d", &n); printf("%d", f(1, n)%10); } 재귀함수를 이용해서 풀어줬다. k는 계산중인 팩토리얼 수이고, t는 곱해야 할 수이다. ​ t가 1이라면 더 곱해줄 필요가 없으므로 k를 결과값으로 반환해주고, 아닐경우에는 k에 t를 ..

슬슬 바텀업 방식 DP의 감이 잡히는거같기도 하고... 그래도 역시 너무 섣부른거 같긴 하다 아직. ​ https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 그냥 dp배열을 1차원으로 만드려다 0으로 시작하는 수는 없다는 규칙때문에 배열을 2차원으로 짜냈다. #include int dp[101][11] = {0}; int index(int k){ if(k==-1){return 10;} return k; } int main(){ int n,sum=0; scanf("%d", &n); for(int i=1; i