분류 전체보기
-
[1120] 문자열BOJ 2022. 2. 14. 17:40
https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 남는 자리는 그리디적으로 Y와 같은 문자로 채워준다고 가정하면, 채워주지 않고 X의 문자를 그대로 사용하는 구간만 탐색하면 된다. 문자열의 길이를 각각 A, B라 하면 하나는 항상 [0, A)까지 비교하고, 다른 문자열에서 [0, B-A]를 시작점으로 갖는 길이 A의 두 문자열을 비교하면 된다. #include using namespace std; strin..
-
[22115] 창영이와 커피BOJ 2022. 2. 13. 02:18
https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 가격이 전부 동일하다고 생각하면 되므로, 사실상 "[12865]평범한 배낭" 과 비슷하게 풀 수 있다. 가격이 1이라고 생각하고, 가격을 최소화하는 느낌으로 접근하자. #include using namespace std; constexpr int INF = INT_MAX >> 1; int n, k, dp[100001], w[101]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; int i, j; fi..
-
[16493] 최대 페이지 수BOJ 2022. 2. 12. 23:07
https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 하나의 챕터를 중복해서 읽지 않는 문제이므로, 역방향으로 갱신하는 배낭문제로 풀 수 있다. #include using namespace std; int n, m, ans, dp[201], w[201], v[201]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int i, j; ..
-
[12034] 김인천씨의 식료품가게 (Large)BOJ 2022. 2. 12. 22:50
https://www.acmicpc.net/problem/12034 12034번: 김인천씨의 식료품가게 (Large) 입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가 www.acmicpc.net n이 작으므로 (v[i]*4)/3 == v[j]를 만족하는 v[i]를 n^2으로 찾으면 된다. #include using namespace std; using ll = long long; ll n; vector v, ans; bool chk[201]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); ll T, ..
-
[2012] 등수 매기기BOJ 2022. 2. 12. 22:29
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 정렬하고, 맨앞부터 1등..2등..3등..으로 매기면 된다. #include using namespace std; using ll = long long; ll ans, n; vector v; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; v.resize(n); ll i; for (i = 0; i > v[i]; sort(v.beg..
-
[2109] 순회강연BOJ 2022. 2. 12. 21:58
https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net i일에 진행되는 강연을 갈지를 판별해야 한다고 보면, [1, i]일에 진행되는 모든 강연을 큐에 넣는다. 큐의 size()가 i보다 크다면, size를 i로 맞추기 위해서 가장 싼 강연부터 빼준다. 로직은 매우 간단하고 직관적인데 구현방식에 대한 고민이 필요하다. 2중 loop로 구현하면 간단하겠지만, 그 경우 강연 선택 여부에대한 bool []이 추가적으로 필..
-
[1941] 소문난 칠공주BOJ 2022. 2. 12. 15:30
https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 백트래킹으로 풀면 3방향 이상의 교차로를 재방문해줄 일이 있어서 방문처리가 까다롭다. 25C7개의 경우의 수를 만들고, 해당 경우의 수가 정답의 가능성이 존재하는지를 판정하는 문제로 바꿔 푸는게 편하다. #include using namespace std; using pi = pair; constexpr int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}; char..
-
[13023] ABCDEBOJ 2022. 2. 11. 04:02
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 백트래킹 하듯 탐색하다, depth가 4가 되었을때 1을 출력한다. #include using namespace std; int n, m; vector adj[2001]; bool vst[2001]; void f(int x, int cnt) { vst[x] = true; if (cnt == 4) { cout n >> m; int i; for (i = 0; i > A >> B; adj[A].push_back(B); adj[B].push_back(A); } for (i = 0; i
-
[16929] Two DotsBOJ 2022. 2. 11. 04:00
https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net dfs로 탐색하다, depth가 4이상일때 시작한 위치를 만났으면 Yes. 모든 시작점에 대해 dfs를 호출해주면 된다. #include using namespace std; const int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}; int n, m, ey, ex; char a[55][55]; bool vst[55][55]; void f(int c..
-
[5397] 키로거BOJ 2022. 2. 11. 03:59
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net list를 사용해서 구현해주면 된다. erase는 it의 한칸 왼쪽을 지우고, erase()가 반환하는걸 그대로 넣어준다. #include using namespace std; int t; list l; string s; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> t; while (t--) { l.clear(); a..