PS 이야기

문제: 공식 홈페이지채점: Yandex 1. prize1부터 v까지의 수가 적힌 크기가 N인 배열이 있다. 수 1의 갯수는 항상 1개고, 1보다 큰 t에 대해 수 t의 갯수는 수 t-1의 갯수의 제곱보다 많다. ask(i)를 호출하면, i보다 왼쪽에 있으면서 작은 수, i보다 오른쪽에 있으면서 큰 수를 알려준다. 이 때, 적은 횟수로 ask(i)를 호출하여 하나 뿐인 수 1의 위치를 찾는 문제다.우선 배열에서 가장 많이 등장하는 수, 즉, 가장 큰..

문제: 공식 홈페이지 채점: Yandex 1. nowruz 이 문제는 빈 칸과 장애물로 이루어진 직사각형 모양의 격자칸에서 빈 칸에 새로운 장애물을 적절히 넣어, 격자판의 빈 칸들을 트리 모양으로 만든다. 이 때, 만들어지는 트리에 포함된 리프 정점 수를 최대화하는 문제다.IOI 2010 Maze 문제와 비슷한 감이 있는 문제다. 문제 세팅 자체도 2차원 격자판이라는 것도 비슷하지만, 최적해가 아니라 최적근접해를 구하는 output only 문제라..

1. 방 배정하기 (room) 수용인원이 A, B, C인 세 종류의 방이 있다. 이 방들을 적절히 예약하여 정확히 N명의 사람이 묵을 수 있도록 하는 문제다. N이 최대 300으로 굉장히 작기 때문에 아래 DP 배열을 정의하고 값을 채우면 된다. D[i] = 정확히 i명의 사람이 묵을 수 있도록 예약할 수 있는가 (있으면 true, 없으면 false) 점화식은 다음과 같다: D[i] = D[i-A] OR D[i-B] OR D[i-C] #..