고동치는고동

시간초과가 떠서 꽤 오래걸렸다.초기에는 가방에 중심을 두고 작은 순서대로 하나씩 봐가면서 가능한 보석중 가장 가치가 큰 보석을 넣는 방법을 생각했다.어처피 뒤에오는 더 큰 가방에서는 앞에 온 작은 가방에 넣을 보석을 넣을 수 있기 때문에 작은 가방은 자신의 입장에서 최적의 보석을 고르면 된다. 근데 가장 가치가 큰 보석을 찾는 방법을 for문으로 N번 돌렸더니 시간 복잡도가 총 O(NK)가 되어 시간초과가 떴다. 따라서 힙구조 우선순위 큐를 사용해서 가장 가치가 큰 보석 찾는 시간을 단축했다. 가방의 크기가 커져서 넣을 수 있는 보석이 더 많아지면 그 보석들을 우선순위 큐에 넣어준다. 그리고 매 가방마다 가장 위의 요소를 pop해서 ans에 더하면 된다. 참고로 우선순위 큐에 들어있는 보석들은 i번째 가..

처음에 DP라는 말에 쉬운줄 알았지만쿠폰과 쉬는 날을 보고 멘붕이 왔다.오래 고민하다가 머릿속에서 꼬여서 포기하고 검색했다. http://wookje.dance/2017/03/06/boj-13302-%EB%A6%AC%EC%A1%B0%ED%8A%B8/ http://wookje.dance/2017/03/06/boj-13302-%EB%A6%AC%EC%A1%B0%ED%8A%B8/ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #define n_ 106#define INF 0x7fffffffusing namespace std; int n, m;int..

Union-find을 써서 시간을 줄이는 건줄 알았는데 그냥 BFS 단순 탐색으로 풀려버렸다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #define n_ 1005using namespace std ; int n, m;int arr[n_][n_];int dx[4] = { 0,1,0,-1 };int dy[4] = { 1,0,-1,0 }; typedef struct Point { int x, y, cnt;}point; queue que; void print(..

별찍기 10과 비슷하게 모두다 *로 초기화 한 뒤 범위를 늘려가며구멍을 송송 뚫으면 된다.단 1개만 구멍을 뚫을 경우 식이 달라야 한다는 점을 조심하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include char arr[3100][6200]; int main(void) { int n; scanf("%d", &n); for (int i = 0; i

전체 사각형을 *로 초기화 한뒤연산을 통해 중간중간에 구멍을 송송 뚫으면 된다.작은 것을 뚫고 점점 더 큰 범위를 뚫으면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include char arr[2200][2200] = {}; int main(void){ int n; memset(arr, '*', sizeof(arr)); scanf("%d", &n); for (int i = 0; i

변수명은 사용자 마음대로 지정한다.배열을 이용하여 구현함tmp는 올림되는 수 123456789101112131415161718192021222324252627282930313233#include using namespace std; int arr[10000]; int main(void) { arr[0] = 1; int n; int k = 1; cin >> n; for (int i = 0; i = 0; i--) { printf("%d", arr[i]); } cout

수학문제 1. 등차수열 문제이다. x+z = 2y 이다.y는 30과 50사이의 40이고 x, y, z의 합은 y가 세번있는 것과 마찬가지 이므로 3y = 120이다. 2. 7의 제곱수의 1의자릿수는 7, 9, 3, 1로 순환한다. 따라서 2014%4해서 2번째인 9가 답이다. 3. 눈으로 보고 구하면 13이 나온다. 4. 직접 식을 세우자시간 = 거리/속력 이므로 총 길의 길이를 a이라고 하면재석이 걸린 시간 a/24+a/8명수가 걸린 시간 2a/45+a/15이다.재석/명수는 (a/6) / (a/9)해서 3/2 5. A+B+C가 A라는 것은 B+C가 10이라는 것이다. 그러면 1이 올림되고 1+A+B+C가 B이므로 A+1 = B이다.덧셈으로 올림되는 수는 1이므로 C는 1 이어서 B는 9 이어서 A는 8..

수학문제 1. 5! 이상은 10의 배수이므로 값에 영향을 주지 않는다. 1!부터 4!은 1, 2, 6, 24 이므로 답은 3 2. 1부터 99까지중 10의 자리에서 1부터 9까지 10번씩 나오고1의 자리에서 10마다 한번씩 10번 나오기 때문에 (1+2+3...+9)*20 = 900 이다.근데 여기서 100의 자릿수의 합을 더해야 하기 때문에 1이 더해진 901이다. 3. 철수가 110바퀴 돌았다는 거는 철수가 3300만큼 달렸다는 것이다.세사람이 동시에 만나는 때는 600만큼 달렸을 때이다. 따라서 5번 만난다. 4. 정말 신기하게도, 1부터 1000까지는 10개의 비트만으로 표현할 수 있으므로동전의 번호를 2진수로 표현한 후 앞에서 부터 순서대로 비트가 1이면 저울에 놓고 아니면 안놓고 해서 10번의..

수학문제 1. 원래라면 얼마부터 가능한지 증명해야 되지만 딱보니 직접 다 해보는게 빠를거 같다. 24원은 7원 두개 5원 두개26원은 7원 세개 5원 한개31원은 위에다가 5원 한개 더33원은 7원 네개에 5원 한개따라서 23원만 못 만든다. 2. 축구대회에서 5팀이 있으면 리그전을 위해서 5*4/2 = 10 경기가 필요하다.그리고 하루에 가능한 경기는 최대 두경기이다. 따라서 5일 3. 먼저 왼쪽부터 하나씩 A B C D E로 두면작은 트리만 보면 B = 2C이다. 따라서 B,C는 2,1 또는 4, 2B,C가 4,2라고 한다면 6 + A*3 = D*2 + E*5 이다.대충 A에 3 D에 5 E에 1을 넣으니 등식이 성립한다따라서 정답은 D에 들어가는 수는 5 4. 먼저 A, B, C는 시간이 되기도 하..

수학문제 1. 일 전체양을 1이라고 하면 A는 한시간에 1/2 B는 한시간에 1/3C는 한시간에 1/6으로 할 수 있다. 셋이 함께하면 1이므로 하루면 된다. 2. 아버지의 나이를 N이라고하면 아들의 나이는 85 - N이다. 과거에 아버지가 85 - N살이었을 때 아들은는 170 - 3N이다.여기서 아버지의 나이는 아들 나이의 6배이면 85 - N = 6(170 - 3N)이다.전개하면 N은 55 아버지는 55 아들은 30따라서 차이는 25 3. 13의 13승의 끝자리수는 3, 9, 7, 1, 3 ... 반복으로 13번째 일의자리수는 3 4. 1000의 약수를 짝지어 나열하고 그 합이 가장 작은 경우를 구한다.1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250,..