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..
A. Nastya and an Array$\!$배열이 주어지는데 하나의 연산을 할 수있다. 배열에 0이 아닌 모든 값에 똑같은 숫자를 더하거나 뺄 수 있다. 그렇게 모든 배열이 0이 되면 멈추는데, 최소연산 횟수를 구하는 문제다. 한번에 연산마다 하나의 숫자를 0으로 바꿀 수 있다. 배열이 똑같은 숫자를 가지면 똑같은 숫자도 모두 0이 되므로 distinct한 숫자의 개수를 세어주면 된다. 숫자가 작으니 bool형 배열로 깔끔하게 처리가능하고, 느리지만 set으로 해도 가능하다. B. Nastya Studies Informatics어떤 수 $a, b$의 $gcd$가 $x$이고, $lcm$이 $y$이다. $a, b$의 범위가 $[l, r]$이다. $l, r, x, y$가 주어졌을 때 가능한 $a, b$쌍의..
A. A Blend of Springtime $\!$꽃 $A, B, C$가 한 줄로 피어있다. 꽃이 시들면 꽃이 있던 위치와 그 양 옆 한 자리에 꽃잎이 떨어진다. 꽃잎이 모두 떨어졌을 때, 한 위치에라도 $A, B, C$의 꽃잎이 모두 떨어져 있으면 Yes를 아니면 No를 출력하는 문제다. 문제 그대로 구현하면 된다. 꽃잎 3개가 모두 있는지 판단하기 위해 배열 3개를 쓸 필요 없이 bit로 처리해주면 하나의 배열로 간단하게 처리 가능하다. B. A Tide of Riverscape$1, 0, '.'$으로 이루어진 기록이 있다. '.'은 각각 0이나 1롤 바꿀 수 있다. 그리고 정수 $p$가 주어지는데 이 정수는 주어진 기록의 주기이다. 여기서 '주기'란 모든 $0
A. Commentary Boxes총 $m$개의 참가팀에게 경품상자를 주는데 $n$개의 상자가 있다. 모든 참가팀에게 동등하게 나누어 주어야하므로 상자수는 $m$으로 나누어 떨어져야만한다. 그러기 위해서 $n$개의 상자 중 몇 개를 버릴 수 있고, 또는 몇 개를 더 만들 수도 있다. 만드는데 드는 비용 $a$와 버리는데 드는 비용 $b$이 주어질 때 $상자수 % m$이 0이 되기위한 최소 비용을 구하는 문제다. 문제 그대로 $(n \% m) * b$와 $(n - (n \% m)) * a$의 최소값을 구하면 된다. B. Micro-World접시에 $n$마리의 박테리아가 살고 있다. 박테리아들은 서로를 잡아먹을 수 있는데, $i$박테리아의 크기 $a_i$가 $j$박테리아의 크기 $a_j$에 대해 $a_i >..
A. Tetriscolumn이 $n$인 맵에서 테트리스를 한다. 테트리스의 블럭은 항상 $1 * 1$짜리가 들어온다. 블럭이 떨어지는 column이 전부 주어지면 총 지워지는 줄 수를 출력하는 문제다. 풀이는 생략. 문제제목을 안 보고 문제부터 읽었는데 문제이해가 너무 어려웠다. 테트리스의 규칙자체를 전부 설명하다보니 이해가 잘 안 됬는데 문제 풀고나니 문제제목이 보여서 실소가 났다. B. Lecture Sleep강의를 듣는데 총 $n$분 듣는다. 매 $i_{th}$분 마다 $a_i$개의 공식을 교수님이 설명해준다. 강의중간에 졸게 되는 경우가 있는데, $t_i$가 1이면 $i_{th}$분에 깨어있는 것이고, 0이면 $i_{th}$분에 졸고 있는 것이며 공식을 듣지 못한다. 강의 중간에 딱 한 번 $k$..
A. Chess Placing$1*n$크기의 체스판이 있다.($n$은 짝수) 체스판은 검흰검흰검흰...순서로 색칠되어있다. 정확히 $n / 2$개의 돌이 체스판위에 놓여져있다. 이 돌들을 움직여서 모두 같은 색깔위에 놓이게 하고싶다. 모두 검정색위에 놓이든 흰색위에 놓이든 상관없다. 이때 돌들이 움직이는 거리의 합의 최소값을 구하는 문제다. 모두 검정칸에 놓는 경우와 흰색칸에 놓는 경우 두 경우를 모두 해보아야한다. 검정칸이든 흰색칸이든 첫 번째 색깔칸에는 가장 왼쪽에 있는 돌이 가야 최소다. 두 번째 색깔칸에는 가장 왼쪽에서 두 번째 있는 돌이 가야 최소다. 난 엄청 복잡하게 풀었는데 풀이보니 엄청 간단하게 풀었다.두 번 틀렸는데 첫 번째는 조금 복잡하게 푸는 바람에 초기에 들어온 돌들은 다른 배열에 ..
