ps하는블로그

A. Colored Balls: Revisited 문제 : 가방에 $n$개 종류의 공들이 있고 각 공들은 $cnt_i$개씩 있다. 서로 다른 색의 공을 하나씩 뽑아 두 개를 가방에서 제거하는데 이를 가방에 남은 공의 종류가 하나가 될 때까지 반복한다. 이때 마지막으로 남아 있을 수 있는 공의 색을 알아보면 된다. 답이 여러 개 있다면 아무것이나 출력하면 된다. 풀이 : 가방에서 가장 큰 $cnt_i$값에 해당하는 색이 답의 후보가 되고 이 중에서 아무것이나 하나만 출력하면 된다. 코드 : #include using namespace std; void solve() { int n; cin >> n; vector ar(n); for (int& x : ar) cin >> x; int ans = 0, m = 0..

A. Mainak and Array 문제 : 길이가 $n$인 수열 $a$가 있다. 수열 $a$의 부분을 선택해서 순서를 유지한 채로 위치를 바꿀 수 있다. 즉 $1\leq l\leq r\leq n$인 $l,r$에 대하여 $a_l = a_{l+1}, a_{l+1}=a_{l+2}, ..., a_{r-1}=a_r, a_r=a_l$의 연산을 원하는 만큼 반복할 수 있다. 이때 $a_n - a_1$의 최댓값을 알아보면 된다. 풀이 : $1 < l\leq r < n$인 경우 연산을 아무리 적용해도 결과는 바뀌지 않으므로 $a_n-a_1$이 답의 후보가 된다. $1 = l\leq r < n$인 경우 $a_1, a_2,..., a_{n-1}$중 최솟값을 $a_1$로 옮긴 후 $a_n$에서 뺀 값이 답의 후보가 된다. ..

A. Madoka and Strange Thoughts 문제 : $n$이 입력으로 주어질 때 $1\leq a,b\leq n$를 만족하는 $a,b$에 대하여 $\frac{lcm(a,b)}{gcd(a,b)}\leq 3$를 만족하는 $(a,b)$쌍이 몇 개 있는지 알아보면 된다. 풀이 : $gcd(a,b)=d$라 하면 $a=a'd, b=b'd$라 할 수 있다.($a',b'$는 서로소) $lcm(a,b)=\frac{ab}{d}$이므로 $\frac{lcm(a,b)}{gcd(a,b)} = \frac{a'b'd^2}{d^2}=a'b'$이라 할 수 있고 $a'b'\leq 3$이므로 $(a': b')$로 가능한 것은 $(1:1), (1:2), (1:3), (2:1), (3:1)$이다. 따라서 $n + 2\times \l..

A. Spell Check 문제 : 길이가 $n$인 문자열이 $s$가 있다. $s$에 $T, i, m, u, r$이 한 번씩만 있으면서 다른 나머지 문자가 없는지 알아보면 된다. 풀이 : 문자열의 각 문자들의 개수를 세주고 $T,i,m,u,r$이 한 번씩만 있는지 보면 된다. 코드 : #include using namespace std; void solve() { string str; int n; cin >> n >> str; int A[30] = { 0, }, a[30] = { 0, }; for (int i = 0; i > s1 >> s2; bool st = true; for (int i = 0; i < n; i++) { int t1 = s1[i] ==..

A. Image 문제 : $2\times 2$크기의 판이 있고 각 원소는 소문자로 되어있다. 한 번의 연산으로 판에서 어떤 값을 다른 값으로 바꿀 수 있을 때 모든 값이 같게 되는 최소 연산 횟수를 구하면 된다. 풀이 : 4개의 문자를 확인해서 서로 다른 문자의 총 갯수에서 $1$을 뺀 값이 답이 된다. 코드 : #include using namespace std; void solve() { char str[3][3]; vector st(30, false); int cnt = 0; for (int i = 0; i > str[i]; for (int j = 0; j < 2; j++) { if (!st[str[i][j] - 'a']) cnt++; st[str[i][j] - 'a'..

A. Crossmarket 문제 : $n\times m$크기의 판에 A, B가 있다. A는 $(1,1)$에서 $(n,m)$으로 가야 하고 B는 $(n,1)$에서 $(1,m)$으로 가야 한다. A, B는 처음에 각각 $(1,1)$, $(n,1)$의 위치에 있고 상하좌우로 $1$칸 움직이는데 $1$의 체력이 필요하다. B가 지나간 자리에는 포탈이 생기는데 만약 A, B가 포탈이 있는 칸에 있다면 포탈이 있는 칸 중 아무 곳이나 1의 체력으로 이동할 수 있다. 이때 A, B가 원하는 목적지까지 가는데 필요한 최소 체력을 구하면 된다. 풀이 : B가 $(1,1)$로 올라간 뒤 $(1,m)$으로 간다고 하면 필요한 체력은 $(n-1) + (m-1)$이다. A는 B가 지나간 경로에 있는 포탈을 사용해서 $(n,1)..

A. Burenka Plays with Fractions 문제 : 정수 $a,b,c,d$가 주어지고 이를 $\frac{a}{b}, \frac{c}{d}$형태로 나타냈을 때 분자 혹은 분모에 $0$이 아닌 특정 값을 곱하는 연산이 있는데 두 값을 같게 하려 할 때 최소 연산 횟수를 구하면 된다. 풀이 : $ad=bc$이면 답은 $0$이다. $\frac{a}{b}$의 분자와 분모에 임의의 정수 $x,y$를 곱하면 $\frac{c}{d}$가 된다고 했을 때, $\frac{a}{b}\cdot \frac{x}{y} = \frac{c}{d}$라 하면 $ad\cdot \frac{x}{y}=bc$라고 할 수 있고 $ad\neq0$일때 $\frac{x}{y} = \frac{bc}{ad}$이다. 여기서 $gcd(ad,bc..

A. Chip Game 문제 : Burenka와 Tonya가 $n\times m$크기의 판에서 게임을 한다. 처음에 $(n,1)$의 위치에 말이 있고 이 말은 오른쪽이나 위로 홀수 크기만큼 움직일 수 있는데 계속 움직이다가 $(1,m)$의 위치가 되면 더 이상 움직일 수 없다. 자신의 턴에 더 이상 움직일 수 없으면 게임에서 지게 된다. 판의 크기가 주어지고 Burenka가 먼저 시작하면서 서로가 자신이 이기는 최선의 방법으로 말을 움직인다고 했을 때 누가 이기는지를 알아보면 된다. 풀이 : 먼저 $1\times m$크기의 판을 생각해봤을 때(오른쪽으로만 이동) 처음 위치한 $(1,1)$칸을 제외하면 움직일 수 있는 칸은 $m-1$개이다. 홀수 크기만큼 움직일 수 있으므로 $m-1$을 홀수들의 합으로 표..