A. K-divisible Sum $n$과 $k$가 주어지면 $n$개의 아무 수를 더 해서 $k$의 배수를 만들고 싶은데, 그 $n$개의 수중 가장 큰 수의 값을 가장 작게 만들고, 그 수를 구하는 문제다. $n$보다 $k$가 작으면 성립하지 않으므로 $n$보다 크면서 가장 작은 $k$의 배수를 구해준다. $n$개의 수를 모두 1로 맞추면 $n$이 나오고, $n+1$은 1,1,1,1.....2, $n+2$는 1,1,1,1.....2,2, $n + (n - 1)$은 1,2,2,2,2....2 이므로 $t*n + alpha$에 대해 $alpha == 0$이면 $t$이고 $alpha != 0$이면 $t + 1$이다. $t*n + alpha = k$를 계산해주면 된다. B. Inflation 매 달의 물건의 가..
전체적으로 쉬웠던 Round다. A. Space Navigation 상하좌우로 움직여야하는 명령 string이 들어왔을 때, 명령 중 아무거나 제거했을 때 목적지에 도달할 수 있는지 판단하는 문제다. 상의 개수, 하의 개수, 좌의 개수, 우의 개수를 전부 더하면 명령을 적절히 제거했을 때 움직일 수 있는 boundary가 나오므로 그 boundary내에 목적지가 있는지 판단하면 된다. B. New Colony 산이 일렬로 있는데, index 0 산에서 돌을 오른쪽으로 굴린다. 만약 높이가 더 높은 산을 만나서 돌이 멈추게 될 경우, 멈춘 그 산의 높이는 1 증가한다. k번째 돌을 굴렸을 때 그 돌이 멈추는 산의 index를 출력해야하는데, 더 높은 산을 만나지 못 해서 산 끝까지 가게 되면 -1을 출력하..
역대 최악의 성적이다. 그도 그럴것이, 낮에 백준에서 다이아2짜리 문제 푼다고 너무 고생해서 머리가 너무 아픈 상태였는데,어쩔 수 없이 진행했다.. 근데, 그럼에도 불구하고 결과를 보면 blue유지가 가능한 점수다. 확실히 요즘 blue는 예전 cyan인듯 하다. A. Yet Another String Game 영어 해석이 안 되서 너무 오래걸렸다. index가 짝수면 'z'에 가깝게, 홀수면 'a'에 가깝게 바꿔주면 된다. B. The Great Hero 직관적으로 공격력이 낮은 녀석부터 패줘야 최적의 답이다. 한 번 제출했는데 틀리길래 공격력 순이 아니라 한 녀석과 전투하는 동안 감소하는 총 체력순으로 패줘야하나? 싶어서 그렇게 접근해봤지만 fail. 나중에 보니 int overflow때문이었다. 집..
A. Add and Divide $a $/=$ b$와 $b $+=$ 1$의 연산 2가지를 해서 $a$를 0으로 만들어야 할 때, 최소 연산 수를 구하는 문제이다. 간단하게, bfs돌리면 $log_2(a)$만에 풀린다. 8분이나 걸린 이유는 $b$가 1일때 때문에 살짝 멈칫했고, visited check 때문에 set을 쓴다고 좀 오래 걸렸는데, 사실 visited check할 필요도 없이 그냥 $log_2(a)$만에 풀린다. B. Replace and Keep Sorted 배열 $b_i$가 $a_i$와 $k$-닮음 이려면 $a_i, b_i$ 모두 단조 증가해야하고, 같은 길이를 가지며, 원소가 $1$~$k$여야 하며 모두 distinct하며 정확히 한 원소만 달라야 한다. 증가하는 배열 $a_i$와 범위..
A. Polycarp's Pockets숫자가 적혀있는 코인이 $n$개 있다. 같은 숫자를 갖는 코인끼리는 같은 주머니에 넣지 못 할때, 필요한 최소 주머니 수를 구하는 문제다. 가장 많은 같은 값을 갖는 코인의 개수를 구하면 된다. B. Binary String Constructing$a$개의 0과 $b$개의 1을 사용하여 string을 구성하는데 $s[i] != s[i + 1]$인 원소의 개수가 총 $x$개 이어야한다. 그런 string을 출력하는 문제다. 먼저, $a$가 더 크다고 가정해보자. 그러면 0으로 string을 모두 채운 후 $b$개의 1을 적절히 박아넣으면 된다. 먼저 $s[0]$ 에1을 넣고 x를 1개 빼자. 그 다음, x가 2 이상일 때 까지 $s[n - 2]$부터 2칸 간격으로 1을..
A. Hit the Lottery1, 5, 10, 20 ,100 단위의 지폐가 있다. 지불해야할 돈을 딱 맞게 지출 하는 최소 지폐 수를 구하는 문제다. greedy하게 100짜리를 쓸 수 있으면 100짜리를 모두 쓰고 20짜리를 쓸 수 있으면 20짜리를 모두 쓰고 하면 된다. B. World Cup총 $n$개의 줄이 있고 그 줄에 서 있는 사람 수가 주어진다. 매 초 마다 모든 줄에 한 명 씩 들어가게 되고, 0명이 되면 그 초에 경기장에 들어 갈 수 있다. 나는 줄을 조금 특이한 방식으로 설 건데, 먼저, 첫 번째 줄에 선 뒤, 매 초 마다 그 줄에서 경기장에 들어갈 수 없으면 바로 오른쪽 줄로 옮긴다. 즉, 그 줄의 사람수가 0이면 바로 들어갈 수 있으니 그 줄로 들어가지만, 아니면 오른쪽 줄로 옮..
A. Mishka and Contestps대회에 참가하는데 나의 ps스킬이 수치상으로 $k$이다. $k$보다 어려운 난이도의 문제는 풀지 못 한다. 문제를 효율적으로 풀기위해 왼쪽부터 $k$보다 작거나 같은 문제들을 풀다가 $k$보다 높은 난이도의 문제를 만나면 오른쪽부터 $k$보다 작거나 같은 문제들을 쭉 푼다. 다시 $k$보다 높은 난이도의 문제를 만나면 문제 풀기를 멈춘다. 총 푸는 문제 수를 구하는 문제다. for문 1개와 bool형 배열 하나면 해결된다. B. Reversing Encryption길이 $n$의 문자열 $s$를 암호화하는 방법은 $n$의 약수를 모두 구하고, 약수를 오름차순으로 정렬한 뒤 각 약수마다 $s$의 부분문자열 $s[1, d]$를 뒤집는다. 암호화된 문자열이 주어지면 문자..
A. If at first you don't succeed...총 $n$명 중 A파티장에 간 인원 $a$명과 B파티장에 간 인원 $b$명, 두 파티장 모두 간 $c$명이 주어진다. 그런데 나는 두 파티장 모두 가지않고 집에 있었다. 파티장에 가지않은 인원을 구하는 문제다. $a,b,c,d$이 불가능한 숫자들이면 -1을 출력한다. $a,b$의 교집합이 $c$명이고 총 표본이 $n$명인데 나는 파티장을 가지않았으므로 $(a \cap b)^c$가 1 이상임이 보장되어야한다. if문 하나로 처리가능하므로 생략. B. Getting an A$n$개의 과목의 점수가 주어지고, 각 과목의 점수는 최대 5점이다. 평균점수가 4.5점만 넘으면 성적표에는 5점으로 기록되는데, 5점으로 기록되기 위해 몇몇과목들을 재수강해야..
A. Fingerprints0~9까지 적혀 있는 키패드가 있다. 수열과 키패드에 지문이 묻어있는 숫자가 주어진다. 비밀번호는 지문이 묻어있는 숫자들로 이루어져있고, 주어진 수열의 가장 긴 부분수열이다. 단, 부분수열은 연속적이지 않아도 된다. 이때 비밀번호를 구하는 문제다. 간단하다. 설명이 필요없다. B. Knights of a Polygonal Table검사들이 서로를 죽이는데, 자기보다 힘이 약한 기사만 죽일 수 있다. 헌데 검사들은 양심이 있어서 $k$명 초과로 죽이지 못 한다. 그리고 검사들은 다른 검사를 죽이고 나면 그 검사의 돈을 모두 가져올 수 있다. 각 검사가 얻을 수 있는 돈의 최대값을 구하는 문제다. 검사들의 power를 오름차순으로 정렬한 뒤 for문으로 올라가면서 가장 큰 $k$개..
A. Mahmoud and Ehab and the even-odd game먼저 내가 숫자 $n$을 선택하고, 상대방 부터 1보다 크거나 같고 $n$보다 작거나 같은 숫자 하나를 말해서 $n$에 뺀다. 나는 홀수만, 상대방은 짝수만 뺄 수 있는데, $n$에 뺄 숫자를 말 할 수 없는 경우 진다. 모두가 최선을 다해서 게임을 할 때 누가 이기는지 구하는 문제다. $n$이 홀수면 상대방먼저 얘기할 수 있으므로 $n$보다 작은 짝수를 뺄 것이다. 그러면 홀수가 남을 것이고, 내가 그 수를 빼버리면 0이 되어 상대방은 더 이상 수를 뺄 수 없으므로 내가 이긴다.$n$이 짝수면 상대방먼저 얘기할 수 있으므로 $n$을 얘기하면 바로 내가 진다. 따라서 $n$이 홀수면 내가, 짝수면 상대방이 이긴다. B. Mahmou..
