온라인저지144 [BOJ] 13900번: 순서쌍의 곱의 합 https://www.acmicpc.net/problem/13900 아... 그냥 재귀 함수로 돌아도 될 텐데 문제 풀 때 이상하게 규칙 찾느라 이렇게 풀었다. 2, 3, 4면 2 * 3 + 3 * 4 + 2 * 4 -> 2(3 + 4) + 3 * 4 이렇게 묶어서 생각했더니 아래 코드가 나왔다. 16ms를 받았는데 더 짧고 빠르게 할 수 있다. #include #include using namespace std; int n; int number[100001]; long long sum = 0; long long sx = 0; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &number[i]); sort(number, numb.. 2018. 7. 27. [BOJ] 11508번: 2+1 세일 https://www.acmicpc.net/problem/11508 어차피 가격 제일 낮은 건 3개 묶은 거에서 공짜이므로 미리 정렬을 시켜놓고 순차적으로 확인하자. (예전에 짠 코드라 sort를 직접 구현했다..) #include #include int price[100001]; void quickSort(int arr[], int left, int right); int main(void) { int n, sum = 0; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &price[i]); quickSort(price, 0, sizeof(price) / sizeof(price[0]) - 1); for (int i = 0; i < n; ++i) { s.. 2018. 7. 27. [BOJ] 9095번: 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 dp[k]: k를 1,2,3의 합으로 나타낼 수 있는 경우의 수 dp[k] = dp[k - 1] + dp[k - 2] + dp[k - 3] k - 1에서 +1을 해서 k를 만들 수 있고 나머지 k-2,k-3도 같은 방식으로 만들 수 있다. #include int memo[11]; int f(int k) { if (memo[k]) return memo[k]; return memo[k] = f(k - 1) + f(k - 2) + f(k - 3); } int main() { int n; scanf("%d", &n); memo[1] = 1; memo[2] = 2; memo[3] = 4; while (n--) { int input; scanf("%.. 2018. 7. 27. [BOJ] 3029번: 경고 https://www.acmicpc.net/problem/3029 입력받은 시간을 모두 초로 바꾼 후, 터질 시간이 현재 시간보다 작을 경우 다음 날이라는 말이므로 24시간을 초로 바꾼 86400초 - 현재 시간 + 터질 시간이 기다려야 하는 시간이다. #include int main() { int ct[3], tt[3]; scanf("%2d:%2d:%2d\n%2d:%2d:%2d", &ct[0], &ct[1], &ct[2], &tt[0], &tt[1], &tt[2]); int cts = ct[0] * 3600 + ct[1] * 60 + ct[2]; int tts = tt[0] * 3600 + tt[1] * 60 + tt[2]; int ans = (cts < tts) ? tts - cts : 86400 -.. 2018. 7. 27. [BOJ] 3042번: 트리플렛 https://www.acmicpc.net/problem/3042 이전 포스트가 CCW였는데 사실 이 문제를 풀기 위해 복습한 것이었다. CCW를 안다면 상당히 쉽게 풀 수 있는 문제였다. 핵심은 ccw이긴 해도 좌표만 따로 저장하는 것도 나름의 스킬인 것 같다. 그러면 더 쉬우니까... 그래서 알파벳들이 있는 x, y 좌표를 3개 잡고 ccw를 확인해서 그 값이 0이면 기록을 증가시키면 된다! #include int n; char A[100][101]; int x[26], y[26], m; int CCW(int x1, int y1, int x2, int y2, int x3, int y3) { int temp = x1 * y2 + x2 * y3 + x3 * y1; temp -= (x2 * y1 + x3 .. 2018. 7. 27. [BOJ] 11758번: CCW https://www.acmicpc.net/problem/11758 문제 그대로 CCW를 구현하는 문제다. 나는 CCW가 뭐 대단히 어려운 거라고 생각했고 그로 인해 좀 꺼려졌는데 이번에 기회가 있어서 다시 보니 그냥 아마 중학교 3학년 때 삼각형 넓이 구하는 공식 해서 '신발끈 공식'을 배운 적이 있었는데 그거였다. 물론 증명은 못하지만... 쓸 수는 있어서 기쁘다. 넓이가 양수면 반시계 방향, 음수면 시계 방향, 0이면 일직선(세 점이)인 것이다. 외우기도 쉬운게 CCW 뜻 자체가 counter clockwise: 반시계이기 때문에 ccw값이 양수면 반시계라는 게 외우기 쉽다. #include int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { in.. 2018. 7. 27. [BOJ] 15595번: 정답 비율 계산하기 https://www.acmicpc.net/problem/15595 문자열을 가지고 숫자놀이할 때는 map가 최고다. 나머지는 구현..? 만 열심히 해주면 된다! #include #include #include using namespace std; int n; double ACpeople = 0; double fail_cnt = 0; map manageNotAC; int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.fixed, cout.precision(14); cin >> n; while (n--) { int submitNum, markResult, memory, time, lang, length; string UserId; cin >> s.. 2018. 7. 27. [BOJ] 3041번: N-퍼즐 https://www.acmicpc.net/problem/3041 원래 위치인 각각의 원래 위치는 ((square[i][j] - 'A') / 4, (square[i][j] - 'A') % 4)인데 맨해튼 거리로 흩어짐 정도를 구해야 하므로 찾아진 x, y의 값을 빼주는 것이다. #include inline int abs(int a) { return a < 0 ? -a : a; } char square[4][4]; int main() { for (int i = 0; i < 4; ++i) scanf("%s", square[i]); int ret = 0; for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) if (square[i][j] != '.') ret +=.. 2018. 7. 27. [BOJ] 3040번: 백설 공주와 일곱 난쟁이 https://www.acmicpc.net/problem/3040 2309번 문제와 똑같다. #include int main() { int dwarf[9] = { 0, }, sum = 0; for (int i = 0; i < 9; ++i) { scanf("%d", &dwarf[i]); sum += dwarf[i]; } int idx1, idx2; for (int i = 0; i < 9; ++i) for (int j = i + 1; j < 9; ++j) if ((sum - dwarf[i] - dwarf[j]) == 100) idx1 = i, idx2 = j; for (int i = 0; i < 9; ++i) { if (i == idx1 || i == idx2) continue; printf("%d\n", .. 2018. 7. 27. [BOJ] 1764번: 듣보잡 https://www.acmicpc.net/problem/1764 정말 듣도보도 못한 문제다. 그 문자열이 두 번 나오면 듣보잡이다. #include using namespace std; struct Info { int count; }; int main() { ios_base::sync_with_stdio(false), cin.tie(0); int N, M; cin >> N >> M; map ms; for (int i = 0; i > tmp; ms.insert(make_pair(tmp, Info())); ms[tmp].count++; } vector v; for (auto &i : ms) if (i.second.count >= 2) v.pus.. 2018. 7. 26. [BOJ] 10539번: 수빈이와 수열 https://www.acmicpc.net/problem/10539 역연산을 해서 구했다. (sum + (input V)) / i = x -> input V = x * i - sum #include int main() { int n, sum = 0; scanf("%d", &n); for (int i = 1, a; i 2018. 7. 26. [BOJ] 2075번: N번째 큰 수 https://www.acmicpc.net/problem/2075 메모리 제한이 10MB인데 1500*1500 크기의 배열에 정렬을 해도 메모리 9.9MB에 640ms로 아슬아슬하게 AC를 받는다 ㅋㅋㅋ 아니면 우선순위 큐(pq라고 하겠다)를 이용하는 방법도 있다. pq는 pop할 때 기본적으로 가장 큰 수가 나오기 때문에 pq 크기가 n보다 클 때 계속 pop하면 pq.top은 가장 큰 수(n번째 큰 수)가 남는다. #include #include using namespace std; int n; priority_queue pq; int main() { scanf("%d", &n); for (int a, i = 0; i < n * n; i++) { scanf("%d", &a); pq.push(-a); .. 2018. 7. 26. [BOJ] 1159번: 농구 경기 https://www.acmicpc.net/problem/1159 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(0); string s; string name[151]; int n, al[26] = { 0, }, cnt = 0; cin >> n; for (int i = 0; i > name[i]; al[name[i][0] - 'a']++; } for (int i = 0; i = 5) { s += (i + 'a'); cnt++; } if (cnt == 0) { cout 2018. 7. 26. [BOJ] 10799번: 쇠막대기 https://www.acmicpc.net/problem/10799 괄호가 닫히는게 막대기의 끝인지 레이저인지 잘 구분해야 한다. '('일 땐 계속 스택에 집어넣는다. ')'일 땐 무조건 pop을 한다. 레이저일 땐, 여태까지 스택에 넣었던 개수 즉, 나열된 막대기의 개수를 더한다. 막대기의 끝에선 항상 막대기 조각 하나만 남기 때문에 그것의 개수(1)을 더한다. #include #include int idx; int main() { int result = 0; char st[100000]; scanf("%s", st); for (int i = 0; i < strlen(st); ++i) { if (st[i] == '(') { idx++; } else if (st[i] == ')' && st[i - 1] .. 2018. 7. 26. [BOJ] 9012번: 괄호 https://www.acmicpc.net/problem/9012 STL에 있는 stack을 이용하면 쉽게 해결할 수 있다. (면 push, ) 일 때 스택이 비어있으면 NO 출력하고 종료, 아니면 pop을 반복한다. 문자열을 다 돌고 마지막에 스택에 뭔가가 있다면 VPS가 아니므로 NO를 출력해야 한다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(0); int T; cin >> T; while (T--) { string s; stack stk; bool flag = false; cin >> s; for (auto &i : s) { if (i == '(') stk... 2018. 7. 26. 이전 1 2 3 4 5 6 ··· 10 다음