슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다.
중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.
마리오는 받은 점수의 합을 최대한 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까지의 수로 구할 수 있다. 이는 반복문 하나만 사용하면 구할 수 있다.
문자열의 일부분을 포함하는 값들을 찾을 때 LIKE절을 사용한다. Column LIKE '표현식' 과 같은 방법으로 사용한다. '표현식'의 형태는 정규표현식과 유사하다. 이 문제에서는 el만 표함되면 된다 했으므로 앞 뒤로 몇개가 있어도 상관없는지를 나타내는 %를 앞뒤로 사용한다.
1
SELECT ANIMAL_ID,NAME FROM ANIMAL_INS WHERE NAME LIKE'%el%' AND ANIMAL_TYPE ='Dog'ORDERBY NAME;
어떤 수 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로 나누면 나머지를 출력하면 된다.
HAVING 절을 사용하는 예제이다. HAVING절은 WHERE절과 비슷하게 조건을 걸어줄 수 있다. 하지만 WHERE절에 조건을 걸 때에는 제약이 없지만 HAVING절은 GROUPBY에 사용한 컬럼에 대해서만 조건을 걸어 줄 수 있다. 따라서 NAME에 대해서 GROUPBY를 걸어주고 count가 1보다 크다는 조건을 걸어서 두 번 이상 쓰인 이름을 파악한다.
1
SELECT name,count(name) as 'COUNT'from animal_ins GROUPBY name HAVING count(name) >1ORDERBY NAME;
