나그네

16922번: 로마 숫자 만들기 문제https://www.acmicpc.net/problem/16922풀이I, V, X, L 네 가지 문자를 N개 사용해 만들 수 있는 조합을 구하면 된다. 단, 각 문자가 의미하는 수가 있고 이 합이 중복되는 경우를 제거해야 한다. 이유는 IXI와 IIX를 같은 12로 보기 때문이다.백트래킹으로 가능한 경우의 수를 모두 만들어보며 visited 배열을 사용해 이미 센 수인지 확인한다. 1, 5, 10, 50 순으로 조합해 보되 예를들어 4가지 문자를 조합하는 경우 1, 1, 1, 5와 1, 1, 5, 1은 같기 때문에 이미 3번째에 5를 고른 경우엔 4번째에 1을 고를 필요가 없어진다. 따라서 5부터만 확인한다.코드#include using namespace std;#d..

Codeforces Round #901 (Div. 2) 문제 세트는 여기서 확인할 수 있다. 문제 A. Jellyfish and Undertale (AC+1 / 38 min) 더보기 타이머가 1초일 때마다 가장 작은 도구를 써주면 된다. 사실 풀이의 이유는 모르지만 직접 손으로 써보고 찾은 규칙대로 코드를 짰다. #include using namespace std; #define int long long signed main() { cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while (t--) { int a, b, n; cin >> a >> b >> n; int ans = b, cnt = 0; for (int i = 0; i < n; i++) { int x;..

Codeforces Round #900 (Div. 3) 문제 세트는 여기서 확인할 수 있다. 문제 A. How Much Does Daytona Cost? (AC / 4 min) 더보기 n 크기의 배열의 서브세그먼트에서 k가 가장 빈도가 높은 수가 되도록 할 수 있는지 여부를 출력하는 문제. 서브세그먼트는 배열의 원소 하나도 가능하므로 배열에 k가 등장하면 YES 아니면 NO를 출력한다. #include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int t; cin >> t; while (t--) { int n, k; cin >> n >> k; int x; string ans = "NO"; for (int i = 0; i < n; ..

Codeforces Round #899 (Div. 2) 문제 세트는 여기서 확인할 수 있다. 문제 A. Increasing Sequence (AC / 6 min) 더보기 배열 a를 입력받고 조건을 만족하는 b의 n번째 원소의 최솟값을 출력하는 문제. b는 반드시 오름차순이어야 하고 b의 n번째 원소가 최소가 되기 위해선 a의 1번째 원소는 1부터 가능한지 검사한다. a와 b의 i번째 원소가 같으면 안되므로 x = 1이라는 변수를 만들고 a의 각 원소에 대해 같으면 +2, 아니면 +1 한다. 기본적으로 오름차순이어야 하니까 +1인데, 만약 원소가 a와 같으면 1 더 증가시키면 된다. x는 b의 n번째 원소 + 1 이므로 x-1 출력. #include using namespace std; int main()..

Codeforces Educational Round #155 (Div. 2) 문제 세트는 여기서 확인할 수 있다. 문제 A. Rigged! (AC+2 / 27 min) 더보기 힘은 들 수 있는 바벨 무게의 최대값, 지구력은 바벨을 들 수 있을 때 가능한 횟수다. 이 문제에선 첫 번째 선수가 우승하기 위한 바벨의 최소 무게를 구하는 문제다. 처음 입력되는 선수의 힘 s와 지구력 e를 기준으로 e가 더 높은 선수만 s, e를 pair로 벡터에 추가한 다음 힘을 기준으로 정렬한다. 만약 그런 선수가 없다면 첫 선수의 힘을 출력한다. 자신보다 힘이 강한 선수가 있다면 우승할 수 없으므로 -1을 출력한다. 자신보다 힘이 강한 선수는 없지만, 횟수를 같거나 많이 하는 선수가 있다면 그 선수가 들 수 있는 무게 + ..

Codeforces Round #895 (Div. 3) 문제 세트는 여기서 확인할 수 있다. 문제 A. Two Vessels (AC / 7 min) 더보기 a, b 중 큰 수와 작은 수를 정해놓고 작은 수와 큰 수에 각각 c를 더하고 빼면서 몇 번 만에 같아지는지 구하는 문제다. 단순 시뮬레이션. #include using namespace std; #define ll long long #define pii pair int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int a, b, c; cin >> a >> b >> c; int small = a > b ? b : a; int big = a > b ? a : ..

Codeforces Round #894 (Div. 3) 문제 세트는 여기서 확인할 수 있다. 문제 A. Gift Carpet (AC / 5 min) 더보기 문자 행렬을 입력받고 좌측 열부터 순서대로 탐색한다. 각각 다른 열에서 v, i, k, a를 순서대로 하나씩 선택할 수 있다면 YES 아니면 NO. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; char a[] = {'v', 'i', 'k', 'a'}; while (t--) { int n, m; cin >> n >> m; vector v(n); int cnt = 0; for (int i = 0; i ..

Codeforces Round #886 (Div. 4) 문제 세트는 여기서 확인할 수 있다. 문제 A. To My Critics (AC / 2 min) 더보기 a, b, c 중 두개의 합이 10 이상이면 yes 아니면 no를 출력하는 문제. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int a, b, c; cin >> a >> b >> c; if (a + b >= 10 || a + c >= 10 || b + c >= 10) cout t; while (t--) { int n, t = 0, idx = -1; cin >> n; for (int i = 0; ..

Atcoder Beginner Contest 322 (ABC 322) 문제 세트는 여기서 확인할 수 있다. 문제 A. First ABC 2 (AC / 1 min 44 sec) 더보기 문자열 s에서 "ABC"가 처음 등장하는 위치가 몇 번째 문자인지 출력하는 문제. 없는 경우 -1을 출력한다. #include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n; string s; cin >> n >> s; if (s.find("ABC") != -1) cout > n >> m >> s >> t; if (t.substr(0, n) == s) { if (t.substr(m - n, n) == s) cout > m; vector v(m)..

20206번: 푸앙이가 길을 건너간 이유 문제 https://www.acmicpc.net/problem/20206 20206번: 푸앙이가 길을 건너간 이유 첫째 줄에는 정수 A, B, C (-10,000 ≤ A, B ≤ 10,000, -100,000 ≤ C ≤ 100,000)가 주어진다. 해당 숫자들은 좌표 평면 상에서 Ax+By+C=0 형태로 표현되는 푸앙이가 지나가는 직선 상의 경로을 나타낸다. (단 www.acmicpc.net 풀이 Ax+By+C=0 형태의 표현되는 직선 상의 경로가 직사각형을 통과하는지 여부를 묻는 문제입니다. Ax+By≤-C 또는 Ax+By≥-C로 식을 바꾸어 생각해야합니다. 문제에서 테두리 위로만 지나가는 경우는 위험지역을 통과하지 않는 것으로 간주한다고 했으므로 등호를 포함해..