[ICPC][2016][예선] 반지름 + 문자 인코딩 (FB)

문제 : 반지름 (ICPC 2016 예선)

n개의 점이 2차원 공간에 주어져 있다. 이 점들을 2개의 집합으로 나누는데, 같은 집합에 속한 가장 먼 두 점 사이의 거리의 합이 최소가 되게 나누고, 이 거리의 합을 구하시오.

풀이 :

$N^{2}$으로 가장 먼 두 점 t1,t2를 구하고, 모든 점에 대해서 이들 중 더 가까운 지점의 집합에 속하게 한다.

문제 : 문자 인코딩 (FB)

a를 1, b를 2, …, z를 26으로 숫자에 대응시키자. 그렇다면 숫자로 이루어진 문자열 ‘123’은 abc에 대응되지만, aw나 lc일 수도 있으므로 총 3개의 문자열에 대응된다. 숫자로 이루어진 문자열이 주어졌을 때 이 문자열에 대응되는 영어 소문자 문자열의 수를 구하는 프로그램을 작성하시오.

풀이 :

가장 마지막에 오는 글자는 숫자 한자리, 또는 가능하다면 두 자리로 되어 있을 것이다. 따라서, 만약 마지막 두 자리 숫자를 문자로 바꿀 수 있다면 (27보다 작다면) S[k+1] = S[k] + S[k-1], 그렇지 않다면 S[k+1] = S[k]