레야몬

1. 문제 N개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다. 돌들을 왼쪽부터 1~N번 돌이라고 하자. i번째 돌의 무게는 \(A_i\)이다. 당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 N번 반복하려고 한다. 돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다. 가장 많은 점수를 얻을 수 있도록 돌을 가져가는 방법을 구하여라. -1- 양의 정수 \(N(1 \leq N \leq 3 \times 10^5)\) -1- B또는 W로만 이루어진 길이 N의 문자열 S가 주어진다. S의 i번째 문자 \(S_i\)는 ..

1. 문제 최백준 조교는 그가 가진 금액을 동전으로 교환하되, 그 개수를 최소화하고자 한다. -1- 최백준 조교가 가진 금액 \(M(10^9 \leq M \leq 10^18)\) -2- 동전의 종류 \(N(1 \leq N \leq 1,000)\) -3- 동전의 금액 \(A_i(1 \leq A_i \leq 10,000)\)가 N개 주어진다. N가지의 동전 중 1원짜리 동전은 항상 존재한다. 동전으로 딱 맞는 금액을 만들 때, 그 최소 개수를 출력하라. 2. 재정의 X 3. 해결 방법 \(M = A[N-1] \times x + r)\)로 나타내어질 수 있고 10,000*10,000은 \(10^9\)보다 작기 때문에 나머지가 r이되도록 동전의 개수를 최소화 하고 나머지는 A[N-1]로 더하는 방법으로 그리디를..

1. 문제 나라에는 1부터 N까지 번호가 매겨진 N개의 공항이 있고 M개의 시간 여행이 가능한 비행기가 있다. \((1 \leq N, M \leq 200,000)\). 비행기 \(j\)는 공항 \(c_j\) 시각 \(r_j\)에서 공항 \(d_j\) 시각 \(s_j\)에 착륙한다. \((0 \leq r_j, s_j \leq 10^9, s_j < r_j is possible)\). 게다가 공항에서 환승할 때는 \(a_i\)만큼의 시간이 걸린다. \((1 \leq a_i \leq 10^9)\). Bessie는 도시 1, 시각 0에서 시작할 때 1부터 N까지의 공항으로 각각 도착했을 때 최단 시각은 얼마인가? -1- N, M -M- \(c_j, r_j, d_j, s_j (1 \leq c_j, d_j \leq ..

1. 문제 ACM 왕국의 왕 Mercer가 있다. 그 왕국에는 하나의 수도와 여러 개의 도시로 이루어져 있다. 원래 짜인 도로 건설 계획이 있었으나 비용 절감을 위해 다음과 같은 규칙을 적용하여 도로를 건설하는데 드는 비용을 최소화하려고 한다. 모든 도시는 서로 갈 수 있는 길이 있어야 한다. 도시에서 수도로 가는 최단 거리는 처음 계획과 달라지지 않는다. -1- 도시의 개수 \(N(1 \leq N \leq 10,000)\), 도로의 개수 \(M(0 \leq M \leq 20,000)\) -M- 연결된 두 도시 u_i, v_i, 도로의 거리 d_i, 도로 건설비 c_i \((1 \leq u_i, v_i \leq N, u_i \leq v_i, 1 \leq d_i \leq 1,000, 1 \leq c_i \..

1. 문제 생략 2. 재정의 생략 3. 실수한 점, 개선할 점 생략 4. 해결 방법 생략 #include #include #include using namespace std; const int MAX_K = 101; const int MAX_N = 101; const int INF = 987654321; int N, K; vector elec(MAX_K); int order[MAX_K]; int chg[MAX_N]; void input() { cin >> N >> K; for(int i=0; i> order[i]; elec[order[i]].push(i); } for(int i=1; i

1. 문제 N명의 학생은 3개의 시험을 치러 각 시험에서 같은 등수의 학생이 없도록 성적이 매겨졌다. A가 B보다 세 번의 시험에서 모두 성적이 좋으면 A가 '대단하다'라고 한다. 또, C라는 학생보다 '대단한' 학생이 없으면 C는 '굉장하다'라고 한다. '굉장한' 학생의 수를 구하시오 -1- \(N(1 \leq N \leq 500,000)\) -3- 각 시험에서 1등한 학생부터 N등한 학생이 순서대로 주어짐. 학생의 번호는 1번부터 N번까지 매겨져 있음. -1- '굉장한' 학생의 수 2. 재정의 3 과목 모두 자신보다 성적이 좋은 성적이 없는 사람의 수를 구하시오. 3. 실수한 점, 개선할 점 X 4. 해결 방법 3가지의 정렬을 이뤄내야 한다. 첫 번째 성적을 기준으로 먼저 정렬을 해보자. 첫 번째 성..

1. 문제 수아는 0에서 출발하여 시간 1마다 x축을 따라 1만큼 움직인다. 수평선에는 n개의 바구니가 있고 각 바구니에는 m개의 사탕이 들어있다. 각 바구니는 \(x_1, x_2, ..., x_n\)에 있다. 사탕을 다 먹는데 0의 시간이 걸린다. 1만큼 시간이 지나갈 때 사탕은 녹아 1만큼 줄어든다. 먹을 수 있는 사탕의 최대 개수를 출력하라. -1- \(n, m(0 \leq n \leq 300, 1 \leq m \leq 1,000,000)\) -n- \(x_i(-10,000 \leq x_i \leq 10,000) (x_i \neq x_j)\) -1- 수아가 먹을 수 있는 사탕의 최대 개수 2. 재정의 X 3. 해결 방법 l번째 사탕을 먹기 위해선 l+1번째 사탕을 먼저, r번째 사탕을 먹기 위해선 ..

1. 문제 1번부터 n번까지 번호가 붙여진 병사가 있다. 지휘관은 번호가 연속하도록 여러 특공대를 나눈다. 각 병사의 전투력은 \(x_i\)이며 이들로 구성된 특공대의 각 병사 전투력 합이 x라고 할 때 이 특공대의 전투력은 \(ax^2+bx+c\)이다. \((a < 0)\). 각 특공대의 전투력의 합의 최댓값을 구하시오. -1- 전체 병사 수 \(n(1 \leq n \leq 1,000,000)\) -1- 세 정수 a, b, c \((-5 \leq a \leq -1, \left| b \right| \leq 10,000,000, \left| c \right| \leq 30,000,000)\) -1- \(x_1, x_2, ..., x_n (1 \leq x_i \leq 100)\) -1- 각 특공대의 전투력 ..