PS 이야기

문제: 공식 홈페이지채점: Yandex 1. prize 1부터 v까지의 수가 적힌 크기가 N인 배열이 있다. 수 1의 갯수는 항상 1개고, 1보다 큰 t에 대해 수 t의 갯수는 수 t-1의 갯수의 제곱보다 많다. ask(i)를 호출하면, i보다 왼쪽에 있으면서 작은 수, i보다 오른쪽에 있으면서 큰 수를 알려준다. 이 때, 적은 횟수로 ask(i)를 호출하여 하나 뿐인 수 1의 위치를 찾는 문제다. 우선 배열에서 가장 많이 등장하는 수, 즉, 가장 큰 수는 등장 빈도가 과반이다. 가장 큰 수가 아닌 수의 최대 갯수는 조건에 따라 472개(1개, 4개, 21개, 446개, ...)다. 첫 번째로 가장 큰 수의 개수를 구하기 위해 최대 473번의 질문을 하여, 가장 큰 수의 위치 중 하나를 찾을 수 있다. ..

문제: 공식 홈페이지 채점: Yandex 1. nowruz 이 문제는 빈 칸과 장애물로 이루어진 직사각형 모양의 격자칸에서 빈 칸에 새로운 장애물을 적절히 넣어, 격자판의 빈 칸들을 트리 모양으로 만든다. 이 때, 만들어지는 트리에 포함된 리프 정점 수를 최대화하는 문제다. IOI 2010 Maze 문제와 비슷한 감이 있는 문제다. 문제 세팅 자체도 2차원 격자판이라는 것도 비슷하지만, 최적해가 아니라 최적근접해를 구하는 output only 문제라는 사실이 비슷하다. 이런 류의 문제는 TopCoder Marathon Match 줄여서 MM에 주로 나오는 것으로 알고 있다. 예전에 maze 문제를 해결할 때, 공부에 도움이 됐던 일루님의 글을 소개하고, 이 문제에 맞는 자세한 풀이는 추후 시간이 나면 추..

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] #include using namespace std; int A, B, C, N; bool D[350]; int main() { cin >> A >> B >> C >> N; D[0] = 1; for (int i=0;i