본문 바로가기

BOJ128

[BOJ] 2775번: 부녀회장이 될테야 https://www.acmicpc.net/problem/2775 D[i][j]: i층 j호의 거주민 수 D[0][i] = i D[i][j] = D[i - 1][for k: 1...j] #include int D[15][15]; int main() { int T; for (int i = 1; i 2018. 8. 4.
[BOJ] 10250번: ACM 호텔 https://www.acmicpc.net/problem/10250 풀이가 2가지 방법이 있다. 하나는 직접 for문을 통해 계산하는 방법. 다른 하나는 규칙을 통해 계산하는 방법. 근데 보통 다른 상황과 엮이지 않고 이 상태에서의 답을 구하는 문제들은 규칙성을 노리고 내는 문제들 같다(개인적인 생각) 규칙 층: (N - 1) % H + 1 호: (N - 1) / H + 1 -1 후에 +1을 해주는 이유는 N과 H가 같은 경우에 발생하는 문제가 있다. H(전체 층수)가 3일 때 N = 3인 경우 N % H로 계산하면 0층이 된다. 그래서 그렇다. 호도 저렇게 해주는 이유가 위와 비슷하다 N == H일 때 N / H + 1이면 1이어야 하는데 2가 된다. #include int main() { int T;.. 2018. 8. 4.
[BOJ] 1967번: 트리의 지름 https://www.acmicpc.net/problem/1967 트리의 지름이란 트리에서 노드 간 가장 긴 길이를 의미한다. DFS를 아무 점에서 시작해서 가장 긴 부분의 위치를 찾는다. 그리고 그 위치에서 DFS를 돌려 가장 긴 부분을 찾는다. 그래서 나온 길이가 트리의 지름이 된다. #include #include #include using namespace std; typedef pair pii; int n, res, idx; vector v[10001]; bool visited[10001]; void DFS(int d, int h) { visited[h] = true; if (d > res) res = d, idx = h; for (auto &i : v[h]) { if (!visited[i.fi.. 2018. 8. 2.
[BOJ] 6603번: 로또 https://www.acmicpc.net/problem/6603 재귀함수로 구현할 수 있는데, 현재 인덱스를 선택하거나 안 하거나 둘 다 재귀함수로 호출을 해서 모든 경우를 출력할 수 있게 된다. 매개변수는 인덱스와 카운트로 설정해줘서 카운트가 6이되면 추가한 숫자들을 출력하도록 하면 된다. 출력용 배열은 vector를 사용할 수도 있지만 일반 배열을 사용하려면 P[cnt + 1](출력용) = S[idx + 1](기존 배열)로 변경해주면 된다. #include using namespace std; int s[50], b[7], N; void printAll(int idx, int cnt) { if (cnt == 6) { for (int i = 1; i = N) return; b[cnt + 1] = s[.. 2018. 8. 2.
[BOJ] 2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 4방향으로 BFS를 돌면 된다. #include #include using namespace std; const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; int n, m; char a[102][102]; int vst[102][102]; struct ED { int x, y; ED(int x, int y) : x(x), y(y) {} }; int BFS(int x, int y) { queue q; q.push(ED(x, y)); vst[x][y] = 1; while (!q.empty()) { int xx = q.front().x, yy = q.front().y; q.pop(); if (xx ==.. 2018. 8. 2.
[BOJ] 11383번: 뚊 https://www.acmicpc.net/problem/11383 제목만 읽었을 땐 되게 간단한 문제일줄 알았지만 생각보단 머리를 써야 하는 문제였다. 첫 줄의 문자열을 A, 둘째 줄의 문자열을 B라고 하면 A[i] == A[i / 2](i: 1...2*N)인지 확인한다. #include using namespace std; int main() { ios_base::sync_with_stdio(false), cin.tie(0); int N, M; cin >> N >> M; array s, c; for (int i = 0; i > s[i]; for (int i = 0; i > c[i]; for (int j = 0; j < 2 * M; ++j) if.. 2018. 8. 2.
[BOJ] 4999번: 아! https://www.acmicpc.net/problem/4999 문제 설명을 제대로 이해하지 못해서 재환이가 말하는 소리는 항상 "aaah"인 줄 알았다. 하지만 아니었다는 점. a의 개수를 세서 재환이가 부족하게 질렀다면 병원에 가게 하면 된다. #include #include using namespace std; int main() { cin.tie(0), ios_base::sync_with_stdio(false); string s1, s2; int cnt = 0, cnt2 = 0; cin >> s2 >> s1; for (auto &i : s2) if (i == 'a') cnt2++; for (auto &i : s1) if (i == 'a') ++cnt; if (cnt 2018. 8. 2.
[BOJ] 1766번: 문제집 https://www.acmicpc.net/problem/1766 위상 정렬 공부할 때 대표적으로 풀어보는 문제인 것으로 생각된다. indegree가 0인 것부터 출력해주는데 그 목록 중에 가능하면 쉬운 것부터 풀어야 하므로 우선 순위 큐를 이용해 해줘야 한다. #include #include #include #include using namespace std; void topo(int vertex, int edge) { vector ad; ad.resize(vertex); vector indegrees(vertex, 0); while (edge--) { int a, b; scanf("%d %d", &a, &b); ad[a - 1].push_back(b - 1); indegrees[b - 1]++; } .. 2018. 7. 27.
[BOJ] 2504번: 괄호의 값 https://www.acmicpc.net/problem/2504 나는 이런 문제가 나올 때마다 내 코딩 실력에 너무 자괴감이 든다... 열심히 해야지... 그 간단한 temp 변수 하나를 생각 못해서 뻘짓을 하고 있었다니!!! 말 그대로 tmp는 괄호가 닫힐 때까지 임시로 값을 저장해 주는 변수다. #include #include using namespace std; char s[31]; int val, tmp = 1; stack stk; int main() { scanf("%s", s); for (int i = 0; s[i]; ++i) { switch (s[i]) { case '(': tmp *= 2; stk.push('('); break; case ')': if (stk.empty()) return.. 2018. 7. 27.
[BOJ] 5845번: Perimeter https://www.acmicpc.net/problem/5845 문제: 밀집이 이어지게 주어지는데 그것의 둘레의 길이를 구하라. 안에 구멍이 생기는 것은 무시한다. 해결: dfs를 가지고 해결할 수 있는데 둘레의 길이를 구해야 하므로 오른손 법칙을 프로그램에 적용시킨다고 생각하면 된다. 그래서 밀집의 좌표에서 시작하는 게 아니라 옆에서부터 벽을 짚고 간다는 느낌으로 생각해야 한다. 그리고 핵심은 바로 set이다. 왜냐면 좌표가 10^6까지 주어지는데 10^12짜리 배열은 선언 자체를 할 수 없기 때문에 set이라는 유용한 도구를 사용해서 좌표를 가지고 놀 수 있게 된다. 내가 허튼짓을 했던 것은 구멍인지 확인하는 함수를 구현하는데 대각선 포함 8방향을 다 봐야 하는데 상하좌우만 보게 해서 문제를 계속 .. 2018. 7. 27.
[BOJ] 10540번: KLOPKA https://www.acmicpc.net/problem/10540 모기를 잡기 위해 필요한 정사각형 박스의 최소 넓이를 구하는 문제다. 그래서 모든 x, y를 돌면서 max_x - min_x와 max_y - min_y 중 더 큰 수의 제곱이 답이 된다. #include #include using namespace std; int main() { int n, MaxX = -987654321, MaxY = -987654321, MinX = 987654321, MinY = 987654321; scanf("%d", &n); for (int i = 0, a, b; i < n; ++i) { scanf("%d %d", &a, &b); MaxX = max(MaxX, a); MinX = min(MinX, a); Max.. 2018. 7. 27.
[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.

티스토리툴바