문제 권위를 자랑하는 레이싱 대회 F7이 열릴 예정이다. F7은 드라이버의 순위가 자주 바뀌기 때문에 사람들에게 인기가 아주 많다. 상근이는 F7 레이싱의 엄청난 팬이지만, 마지막 레이싱과 중간고사가 겹쳐서 갈 수 없게 되었다. 지금은 마지막 레이싱을 제외한 나머지 레이싱이 모두 종료된 상황이다. 상근이는 우승을 할 수 있는 사람의 수를 알아보려고 한다. F7의 우승자는 각 레이싱을 통해서 얻은 점수의 합이며, 점수가 가장 높은 사람이 우승을 하게 된다. 마지막 레이싱에서 1등을 한 사람은 N점을 얻게 되고, 2등은 N-1점, ..., 꼴등은 1점을 얻게 된다. 각 레이싱에서 두 드라이버의 등수가 같은 경우는 없다. 마지막 레이싱을 하기 바로 전에 각 드라이버의 점수가 주어졌을 때, 우승을 할 가능성이 ..
문제 선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다. 호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다. 선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다. 어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다. 패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다. 파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어..
문제 n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까? 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 2^31-1 을 넘지 않는 두 자연수 n(n ≥ 1)과 k(0 ≤ k ≤n)로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 2^31보다 작은 경우만 입력으로 주어진다. 문제풀이 고등학교 수학 문제인 조합이다. 이 조합을 계산하는 문제인데, 함정카드가 하나 있다. 바로 n의 범위가 2^31-1이라는 것이다. 이것을 계산하면 2,147,483,648이다. 대략 21억이다. 즉, 시간복잡도가 O(n)인 함수를 짠다고 하더라도 1초 내에 클리..
문제 N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다...
문제 매일 밤, 정인이는 상근이에게 이메일을 보낸다. 정인이는 자신의 이메일이 해킹당할 수도 있다는 생각에, 내용을 항상 암호화해서 보낸다. 정인이가 사용하는 암호 알고리즘은 다음과 같다. 정인이가 보내는 메시지는 총 N글자이다. 먼저, 정인이는 R