슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다.
중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.
마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다.
버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.
입력:
총 10개의 줄에 각각의 버섯의 점수가 주어진다. 이 값은 100보다 작거나 같은 양의 정수이다. 버섯이 나온 순서대로 점수가 주어진다.
출력:
첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.
풀이방법:
반복문을 사용해서 0개 버섯을 먹은 경우부터 10개의 버섯을 먹은 모든 경우를 모두 한 배열에 담아 넣는다. 그 다음에는 python의 sort의 key 기능을 사용해서 100과 가까운 수가 제일 앞에 오도록 정렬을 했다. (abs(x-100)을 이용해서) 그 다음에는 98과 102와 같이 간격이 같은 경우가 있을 수 있으므로 이 경우에는 1번째 인덱스를, 아닌 경우에는 0번째 인덱스를 출력하도록 했다.
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 RxC인 격자판으로 나타냈고, 1x1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r,c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r,c)는 r행 c열을 의미한다.
공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r,c)에 있는 미세먼지의 양은 Ar,c 이다.
1초 동안 적힌 일이 순서대로 일어난다.
1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r,c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c / 5 이고 소주점은 버린다.
- (r,c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)x(확산된 방향의 개수) 이다.
N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.
입력:
첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.
출력:
첫 줄에 구하고자 하는 수를 출력한다.
풀이방법:
몫과 나머지가 같다고 가정한 뒤에 역으로 그 자연수 값을 찾도록 하면 된다. 나머지가 나올 수 있는 경우의 수는 N일 때 0~N-1까지 있다. 따라서 몫과 나머지가 같은 수는 i*(N)+i, i는 0부터 N-1까지의 수로 구할 수 있다. 이는 반복문 하나만 사용하면 구할 수 있다.
어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만든는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev(X) = 1이다.
두 양의 정수 X와 Y가 주어졌을 때, Rev(Rev(X) + Rev(Y))를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 수 X와 Y가 주어진다. X와 Y는 1,000보다 작거나 같은 자연수이다.
출력:
첫째 줄에 문제의 정답을 출력한다.
풀이방법:
파이썬에 문자열을 뒤집는 방법은 크게 두가지가 있다. 첫번째는 문자열을 배열로 바꾼 뒤에 reverse로 뒤집고 다시 join을 사용해서 문자열로 만드는 방법이다. 이 방법은 번거로운 작업이 많이 필요하다. 두번째는 슬라이싱의 특징을 이용하는 방법이다. [ : ]와 같이 사용하면 해당 문자열의 전체를 의미하게 된다. 이 때 [ : :-1]와 같이 사용하면 뒤에서부터 해당 문자열의 전체를 가져오게 된다. 즉 문자열을 뒤집게 된다. 따라서 이를 이용해서 문제가 요구하는 조건대로 연산을 진행하면 답을 구할 수 있다.
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 A,B,C가 빈 칸을 사이에 두고 순서대로 주어진다. A,B,C는 모두 2,147,483,647 이하의 자연수이다.
출력:
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
풀이방법:
주어질 A,B,C의 값이 매우 크므로 pow 연산을 활용하는 것은 시간초과가 발생하게 될 것이다. 따라서 효율적인 연산이 필요하다. 그러면서 사용하게 되는 것이 모듈러 연산의 분배법칙이다.
모듈러 X=x1*x2라고 가정하자. 그러면 X mod y = (x1 mod y)*(x2 mod y) mod y 가 성립한다. 이 것과 10^n*10^m=10^(n+m)임을 사용하면 시간복잡도를 O((logN)^2)까지 줄일 수 있다.
우선 지수를 2의 지수 단위로 분할한다. 이 문제의 예시와 같은 경우 11은 8+2+1로 482는 256+128+64+32+2와 같이 분할할 수 있다. 즉 10^11 mod 12 = (10^8 mod 12)(10^2 mod 12)(10^1 mod 12) mod 12 이고, 10^482 mod 12 = (10^256 mod 12)(10^128 mod 12)(10^64 mod 12)(10^32 mod 12)(10^2 mod 12) mod 12가 된다.
2의 지수를 사용하는 것에는 이유가 있다. 10^1부터 DP 방식을 사용하면 나머지의 값들도 쉽게 구할 수 있기 때문이다. 10^2 mod 12 = (10^1 mod 12)(10^1 mod 12) mod 12 이고 10^4 mod 12 = (10^2 mod 12)(10^2 mod 12) mod 12 ...와 같이 구하면 된다.
위와 같이 dp table을 다 채우고 난 뒤에 해당하는 값들만 곱한뒤에 다시 c로 나누면 나머지를 출력하면 된다.
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
입력:
첫째 줄에 자연수 S(1<=S<=4294967295)가 주어진다.
출력:
첫째 줄에 자연수 N의 최댓값을 출력한다.
풀이방법:
최대한 많은 서로 다른 수를 사용하며 그 합들이 S가 되도록 만들기 위해서는 1부터 차례대로 값을 더하는 것이 가장 많이 사용할 수 있다. 즉 예를 들어 11을 만들기 위해서는 1+2+3+4+1=11과 같이 사용하는 것이 N이 최대가 된다. 하지만 1을 중복해서 사용했다. 그래서 이 1을 4에다가 붙여서 다음과 같이 식을 구성하고 이 것이 최댓값이 되게 된다. (1+2+3+5=11)
따라서 S를 알 때, 자연수 N의 최댓값을 구하기 위해서 일반화를 할 수 있다. 1+2+ .... + n의 합은 S를 넘지 않는다. 즉 1+2+ .... + n +a =S가 되게 되는 것이다. 이 a를 항상 n에 붙임으로써 N의 최댓값을 구할 수 있다. 즉 1부터 n까지의 합이 S와 근접할 때 N의 최댓값이 된다.
1+2 + .... + n = ((n+1)*n)/2 이므로 이를 활용해서 m을 추정할 수 있고 이 값을 하나씩 감소시키며 n을 찾을 수 있다.
두 정수 N과 F가 주어진다. 지민이는 정수 N의 가장 뒤 두 자리를 적절히 바꿔서 N을 F로 나누어 떨어지게 만들려고 한다. 만약 가능한 것이 여러 가지이면, 뒤 두 자리를 가능하면 작게 만들려고 한다.
예를 들어, N=275이고, F=5이면, 답은 00이다. 200이 5로 나누어 떨어지기 때문이다. N=1021이고, F=11이면, 정답은 01인데, 1001이 11로 나누어 떨어지기 때문이다.
입력:
첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수다. F는 100보다 작거나 같은 자연수이다.
출력:
첫째 줄에 마지막 두 자리를 모두 출력한다. 한자리이면 앞에 0을 추가해서 두 자리로 만들어야 한다.
풀이방법:
N을 입력 받은 뒤에 가장 뒤 두 자리를 00으로 만드는 것으로부터 시작한다. 이후 이 값이 F로 나누어지면(나머지가 0이면) 이 값을 출력하고, 나누어지지 않는다면(나머지가 0이 아니라면) F로 나눈 것의 몫에 1을 더한 것에 F를 곱한 것이 최솟값이면서 나누어 떨어지는 수가 된다. 이 때 한자리면 앞에 0을 추가해줘야 하므로 미리 string으로 바꿔서 이를 방지한다.
NxN 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.
각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 게임 판의 크기 N(4<=N<=100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.
출력:
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수를 2^63-1보다 작거나 같다.
풀이방법:
dp를 사용해서 값을 누적시키면서 진행하면 답을 구할 수 있다. 갈 수 있는 경로의 수만 알면 되므로 dp[i][j]로 갈 수 있는 경우의 수를 누적시키면서 n,n으로 진행해나가면 된다. 따라서 시간복잡도는 O(N^2)이 될 것이다. dp[i][j]로 갈 수 있는 방법은 크게 두 가지다. 해당 위치를 기준으로 왼쪽에서 오거나 위쪽에서 오는 경우이다. 해당 칸에서 이동이 가능한지 알아보고 가능하다면 값을 더해주는 방식으로 진행하면 된다.
문자열처리를 해야하는 문제이므로 정규표현식을 사용했다. 정규표현식에서 '\d+'는 숫자를 의미하고, '\D+'를 의미하므로 문자열을 숫자와 숫자가 아닌 것들로 분할하는 작업을 먼저 했다. 문자들을 가져온 배열을 보면 * 과 #이 붙어있는 경우가 있을 수 있으므로 길이로 이를 파악하였다. 길이가 2면 특수문자가 붙어있고, 아니면 문자만 있는 것으로 판단했다. 그 이외에는 해당하는 명령어에 따라서 점수를 부여해주면 된다.
