분류 전체보기
-
[7453] 합이 0인 네 정수BOJ 2022. 3. 12. 04:39
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net O(N^4)는 시간 초과가 나오지만, O(2*(N^2))은 통과할 수 있는 수준이다. '중간에서 만나기'와 비슷한 방식으로, 4개의 집합 A, B, C, D를 2개의 집합 A+B, C+D로 나누어 투포인터를 할 수 있다. 다른 방법으로는 A+B에서 나올 수 있는 값을 전부 저장해두고 C와 D의 2중 루프에서 -(c+d)를 이분탐색할 수 있다. 모든 경우의 수를 탐색하기 위해서, ..
-
[2281] 데스노트BOJ 2022. 3. 12. 04:32
https://www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net dp(i, j) = i번째 이름의 마지막 문자가 j번째 열에서 끝났을때의 최적해로 놓고, i번째 이름을 새로운 행에 쓰는 경우는 항상 고려하며, i번째 이름을 기존의 행에 이어서 쓰는 경우에는, (남은 칸)+(i번째 이름의 길이)= n) return 0; if (dp[i][c] != -1) return dp[i][c]; if (c == m + 1) return f(..
-
[2002] 추월BOJ 2022. 3. 9. 23:58
https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 터널에서 나온 차량번호를 기준으로 볼때, 현재 차량보다 더 늦게나온 차량이 터널에 더 먼저 진입한 경우를 확인한다. 터널에 나온 시점을 map로 관리하자. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using..
-
[1662] 압축BOJ 2022. 3. 9. 17:51
https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 구현이 어려운 문제, N~N^2에 풀리는 문제인데도 N=50으로 꽤나 제한이 널널하다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; string s; ..
-
[1256] 사전BOJ 2022. 3. 6. 15:52
https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 꽤 자주 보이는 조합론&dp 문제 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; ll n, m, k, dp[201][201]; ll c(ll A, ll B) { retu..
-
[15684] 사다리 조작BOJ 2022. 3. 6. 15:47
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹으로 풀때, 사다리의 조작여부를 판별하는 부분은 하나의 열이 조작되지 않은 순간 바로 false를 return한다. 이전의 인덱스를 기억하여야, check()의 호출횟수를 더욱 줄일 수 있고 사다리를 작은 횟수부터 놓아야 check()가 true일때 바로 정답을 출력하고 exit()할 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE co..
-
[15810] 풍선 공장BOJ 2022. 3. 4. 00:56
https://www.acmicpc.net/problem/15810 15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 www.acmicpc.net 우선순위큐로도 풀릴것만 같은 문제다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; ll n, m, ans; vector..
-
[6236] 용돈 관리BOJ 2022. 3. 2. 20:48
https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net i일에 사용할 돈을 a[i]라고 입력받은 뒤, 초기에 가진 돈(cur)을 하나의 mid에 대해서 cur-a[i]가 음수인 경우에는 남은 돈을 통장에 넣고, mid만큼 통장에서 인출한다. 인출한 횟수(cnt)를 매번 기록해 두었다가, n번에 걸친 시뮬레이션이 끝나면 cnt a[i]; int s = 0, e = (int)(1e9 + 0.5); ans = e; while (s > 1; bool ret = f..
-
[2512] 예산BOJ 2022. 3. 2. 20:45
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 모든 예산을 배정할 수 있는 경우에만 예외처리해주면, 그 외에는 간단하다. 입력된 예산 요청액에 대해서, min(a[i], mid)를 누적해주고, 누적된 값이 총예산액을 초과하는지를 판별한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = tru..
-
[4195] 친구 네트워크BOJ 2022. 3. 2. 12:25
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 일단 문자열을 숫자로 바꿔놓고 생각하면 두 정수형 A, B에 대해 union(A,B)를 해준다. p[]의 값을 트리의 크기로 놓으면, abs(find(A))가 답이 된다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif..