전체 글
-
[16165] 걸그룹 마스터 준석이BOJ 2021. 12. 1. 17:09
https://www.acmicpc.net/problem/16165 16165번: 걸그룹 마스터 준석이 정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 www.acmicpc.net 멤버 목록에 대한 쿼리에 쓸 맵과 팀의 이름에 대한 쿼리에 쓸 맵을 구성하고, 멤버목록은 정렬시켜둔다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; int n, m; map mp; map grp; int main(void) { cin >..
-
[10157] 자리배정BOJ 2021. 12. 1. 16:49
https://www.acmicpc.net/problem/10157 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 여러가지 구현 방법이 있겠지만, r*c가 100만뿐이 안되므로 모든 칸을 순회하도록 구현해도 괜찮다. 재귀를 이용해서 다음에 방문할 좌표에 대해서, (좌표가 범위를 벗어나는 경우) || (이미 방문한 좌표) 일때에는 방향을 회전하고 그 외에는 정상적인 탐색범위이므로 방향을 회전하지 않고 그대로 진행한다. 이경우 O(R*C)의 시간복잡도가 나온다. 이문제는 위처럼 구현해도 TLE가 ..
-
[6590] 덧셈 체인BOJ 2021. 11. 30. 05:14
https://www.acmicpc.net/problem/6590 6590번: 덧셈 체인 다음과 같은 네 가지 조건을 만족하는 자연수 수열 을 n에 대한 덧셈 체인이라고 한다. 1. a0 = 1 2. am = n 3. a0 < a1 < a2 < ... < am-1 < am 4. 각각의 k(1 ≤ k ≤ m)에 대해서, ak = ai + aj를 만족하 www.acmicpc.net 처음엔 2진수 비슷하게 접근했는데, 4번 조건이 두 자연수가 아닌 임의의 자연수의 합이라면 올바른 접근이긴 하다. 다만, 중복을 포함하여 2개를 선택해야 하므로, 2진수나 비트적인 접근이 불가능한것으로 보인다. n이 100이라서 브루트포스가 제대로 돌아가기 힘든것처럼 보였지만, 가지치기를 잘 해주면 괜찮다. 현재 상태에서 갈수있는..
-
[11023] 더하기 3BOJ 2021. 11. 29. 13:54
https://www.acmicpc.net/problem/11023 11023번: 더하기 3 첫째 줄에 N(1 ≤ N ≤ 100)개의 수가 공백으로 구분되어서 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 또, 0으로 시작하는 수는 주어지지 않는다. www.acmicpc.net eof 입력되기 전까지 누적합해서 출력하면 된다. 개인적으로 eof처리는 while()안에 넣는 것보단, 별도의 if로 체크하는게 조금 더 가독성이 높아보인다. 1 2 3 4 5 6 7 8 9 10 11 12 13 #include using namespace std; int n, ans; int main(void) { for (;;) { int x; cin >> x; if (cin.eof() == tr..
-
[15665] N과 M (11)BOJ 2021. 11. 29. 13:41
https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 중복을 제거하기 위해 set를 사용한다. set 자체가 정렬이 되므로 입력받을때에 정렬하는 부분(25라인)은 꼭 필요한 부분은 아니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include using namespace std; int n, m; vector v; set s; i..
-
[15656] N과 M (7)BOJ 2021. 11. 29. 13:33
https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 정렬하고, 백트래킹을 진행하는 for의 범위를 [0, n)으로 구현하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; int n, m; vector v; vector cur; void f(void) { int i, j; if (cur.size..
-
[15664] N과 M (10)BOJ 2021. 11. 29. 12:41
https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 비내림차순 조건은 입력받은 수열을 오름차순 정렬함으로 해결한다. 중복제거는, set를 이용해서 해결할 수 있다. 입력되는 수의 개수가 작기 때문에, MLE이 발생하지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int n, m; int main(void) { cin..
-
[1253] 좋다BOJ 2021. 11. 28. 17:51
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 우선 2개를 고르며, 여기에서 O(N^2)을 소모한다. [0, n) 사이의 i, j에 대해서 i n; v.resize(n); int i, j, k, ans = 0; for (i = 0; i > v[i]; sort(v.begin(), v.end()); for (i = 0; i
-
[1015] 수열 정렬BOJ 2021. 11. 27. 12:14
https://www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 수가 작고/수가 같으면 인덱스가 작은순서로 정렬해주면 된다. nlogn으로 구현할 수 있지만, n^2이어도 n> n; int i, j; for (i = 0; i > x; q.push({x, i}); } memset(b, -1, sizeof(b)); for (i = 0; i