문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다. 문제풀이 딱 보면 작은 문제가 반복되어서 큰 문제를 풀 수 있는 전형적인 다이나믹 프로그래밍 문제라는 것을 알 수 있다. 이런 문제라는 것을 눈치 챘다면, 점화식이 어떻게 될지를 생각해봐야 한다. 점화식을 생각하는 방법은 생각보다 간단했다. 경우를 나누고, 그 경우를 메모리제이션을 통해서 풀 수 있게 생각을 하면 된다. 나 같은 경..
문제 단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만 이루어져 있다. 단어와 다른 문자(마침표, 숫자, 심볼, 등등등...)로 이루어진 글이 주어졌을 때, 가장 긴 단어를 구하는 프로그램을 작성하시오. Apple의 길이는 5, son-in-law는 10, ACM-ICPC는 8이다. 입력 입력은 여러 줄, 문단으로 이루어져 있다. 하지만, 10,000글자를 넘지 않는다. 단어의 길이는 100을 넘지 않는다. E-N-D는 입력의 마지막을 의미한다. 출력 가장 긴 단어를 소문자로 출력한다. 가장 긴 단어가 여러개인 경우에는 글에서 가장 먼저 나오는 것을 출력한다. 문제풀이 이 문제는 경우를 정확히 나누는 것으로부터 문제 풀이가 시작이 된다. 경우를 먼저 간단히 나누면 다음과 같다. 1. 단어는 반드시 알파..
문제 수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오. 즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다. 입력 첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다. 출력 첫째 줄에 답을 출력한다. 문제풀이 나는 다음과 같은 아이디어로 시간을 단축해서 풀었다고 생각을 했는데, 다른 분들 답안 제출하신 것들을 보니 O(n) 혹은 O(nlogn) 수준으로 시간복잡도를 줄일 수 있을 것으로 보인다. 내가 푼 방법은 굉장히 단순했는데, 아이디어는 이렇다 ((a1-..
문제 권위를 자랑하는 레이싱 대회 F7이 열릴 예정이다. F7은 드라이버의 순위가 자주 바뀌기 때문에 사람들에게 인기가 아주 많다. 상근이는 F7 레이싱의 엄청난 팬이지만, 마지막 레이싱과 중간고사가 겹쳐서 갈 수 없게 되었다. 지금은 마지막 레이싱을 제외한 나머지 레이싱이 모두 종료된 상황이다. 상근이는 우승을 할 수 있는 사람의 수를 알아보려고 한다. F7의 우승자는 각 레이싱을 통해서 얻은 점수의 합이며, 점수가 가장 높은 사람이 우승을 하게 된다. 마지막 레이싱에서 1등을 한 사람은 N점을 얻게 되고, 2등은 N-1점, ..., 꼴등은 1점을 얻게 된다. 각 레이싱에서 두 드라이버의 등수가 같은 경우는 없다. 마지막 레이싱을 하기 바로 전에 각 드라이버의 점수가 주어졌을 때, 우승을 할 가능성이 ..
문제 선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다. 호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다. 선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다. 어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다. 패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다. 파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어..