나그네

29767번: 점수를 최대로 문제 https://www.acmicpc.net/problem/29767 29767번: 점수를 최대로 단대소프트고에는 교실 $N$개가 있다. 교실은 $1$번부터 $N$번까지 $1, 2, \ldots, N$ 순서로 연달아 있다. 학교 밖에는 $K$명의 학생들이 있다. $K$명의 학생은 학교에 들어가기 전 학생마다 목적지 교실 www.acmicpc.net 풀이 목적지 i번 교실에 도착하면 1~i번 방의 점수를 얻습니다. 즉, 누적합 배열로 i번 교실을 목표로 했을 시 얻는 점수를 저장합니다. K명의 학생들은 서로 다른 목적지를 가지므로 누적합 배열을 내림차순 정렬하고 앞에서부터 K개 원소의 합을 출력하면 됩니다. 코드 #include using namespace std; #def..

29766번: DKSH 찾기 문제 https://www.acmicpc.net/problem/29766 29766번: DKSH 찾기 첫째 줄에 문자열이 입력된다. 문자열의 길이는 $1\,000$을 넘지 않는다. www.acmicpc.net 풀이 입력받은 문자열의 i(0 ~ N-1)인덱스 부터 4글자씩 비교하며 DKSH가 나올 때마다 개수를 세면 됩니다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s, a = "DKSH"; int cnt = 0; cin >> s; for (int i = 0; i < s.size(); i++) { int flag = 0; for (int j = 0; j < 4..

Round #897 (Div. 2) 대회 https://codeforces.com/contest/1867 Dashboard - Codeforces Round 897 (Div. 2) - Codeforces codeforces.com 푼 문제 A. green_gold_dog, array and permutation 입력받은 배열을 오름차순으로 정렬한 다음 원래 index의 위치에 1~N까지 위치하도록 한다. pair를 사용해 index를 함께 묶어서 정렬했다. 어렵지 않아서 코드만 봐도 이해가 될 듯. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n..

29158번: 큰 수 만들기 게임 문제 https://www.acmicpc.net/problem/29158 29158번: 큰 수 만들기 게임 성현이와 지훈이는 큰 수 만들기 게임을 하고 있다. 성현이는 양의 정수 $N$이 적힌 카드 $1$장이 들어 있는 주머니를 들고 있다. 지훈이는 성현이의 카드를 몰래 본 다음 성현이의 카드에 적힌 $N$ www.acmicpc.net 풀이 큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다. 각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다. 먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2..

29160번: 나의 FIFA 팀 가치는? 문제 https://www.acmicpc.net/problem/29160 29160번: 나의 FIFA 팀 가치는? 첫 번째 줄에 선수의 수 $N$과 $K$가 공백으로 구분되어 주어진다. $(0\leq N\leq 1\,000\,000;$ $1\leq K\leq 50\,000)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $i$번째 선수의 포지션 $P_{i}$, 선수 가치 $W_{i}$가 www.acmicpc.net 풀이 항상 가치가 가장 높은 선수를 선발하는 과정을 반복하기 때문에 우선순위 큐(최대 힙)를 사용한다. 11개의 포지션 번호별로 선수를 저장할 수 있는 우선순위 큐 배열을 만든다. 각각의 포지션 번호별로 비어있는 우선순위 큐를 제외하고 한 명씩 선수를..

29159번: 케이크 두 개 문제 https://www.acmicpc.net/problem/29159 29159번: 케이크 두 개 $(0,0),(0,1),(1,0),(1,1)$이 네 쪽지점인 직사각형과 $(2,1),(3,2),(3,1),(3,2)$가 네 꼭지점인 직사각형을 동시에 이등분하는 직선의 방정식은 $y=\frac12 x+\frac14$이다. www.acmicpc.net 풀이 두 직사각형 각각의 중심 좌표를 구하고, 두 점을 지나는 일차방정식을 구하는 문제다. 분수 형태의 출력 형식 때문에 애를 먹은 문제다. 먼저 일차방정식의 형태를 보면 y - y1 = ((x2 - x1)/(y2 - y1))(x - x1)이다. y = Px + Q 형태로 나타냈을 때 P와 Q를 출력하는 문제다. 먼저 기울기 P ..

29156번: 탭 UI 문제 https://www.acmicpc.net/problem/29156 29156번: 탭 UI 탭 UI는 여러 탭이 일렬로 나열되어 특정 탭을 클릭하면 해당 탭에 대한 내용을 확인할 수 있는 UI(User Interface)이다. 화면 내에 있는 탭은 노출되고 좌우로 화면을 벗어난 탭은 노출되지 않으며 사 www.acmicpc.net 풀이 각 탭의 길이를 입력받을 때 누적합(prefix_sum) 배열을 만들어 전체 길이를 기록한다. 그리고 각각의 탭의 중앙의 좌표를 저장한 coordinate 배열을 만든다. 화면의 길이의 절반(화면의 중앙)을 mid라고 한다. 그리고 클릭한 탭 x가 주어졌을 때, mid에 위치하기 위해 coordinate[x]가 얼마나 이동해야 하는지를 gap이..

29155번: 개발자 지망생 구름이의 취업 뽀개기 문제 https://www.acmicpc.net/problem/29155 29155번: 개발자 지망생 구름이의 취업 뽀개기 난이도 $1$에서 $1$분, $4$분, $4$분 순서로, 난이도 $2$에서 $5$분, 난이도 $3$에서 $20$분, 난이도 $4$에서 $40$분, 난이도 $5$에서 $100$분 순서대로 풀면 $1+3+4+0+4+60+5+60+20+60+40+60+100=417$분이 걸린다. www.acmicpc.net 풀이 각 난이도 별로 문제를 푸는 데 걸리는 시간을 저장하고 오름차순으로 정렬한다. 각 난이도별로 풀어야하는 문제의 수만큼 앞에서부터 고르면 된다. 이 문제에서는 문제를 푸는 데 필요한 시간을 최소화하고 휴식시간도 최소화해야한다. 휴식..

28683번: 피타! 피타! 피타츄! 문제 https://www.acmicpc.net/problem/28683 28683번: 피타! 피타! 피타츄! 포켓몬스터를 좋아하는 종우는 포켓몬스터를 연구하다가 포켓몬스터가 상당히 수학적이고 코딩과 밀접한 관련이 있는 게임이라는 것을 알게 되었다. 모든 이동은 유클리드 공간에 평행하게 이 www.acmicpc.net 풀이 대회 당시에는 문제를 해결하지 못했다. 친구의 설명으로 문제를 해결하고 에디토리얼을 참고했다. 몇 가지 조건을 나누어 문제를 해결할 수 있다. 1. n이 제곱수인 경우 √n은 정수다. 임의의 정수 a에 대해 (√n, a, √(n+a^2))이 직각삼각형을 이루고, 두 변의 길이가 √n과 a로 정수이므로 무한하다. 2. n이 제곱수가 아닌 경우 나머지..

28682번: 재우야 임관하자 문제 https://www.acmicpc.net/problem/28682 28682번: 재우야 임관하자 인터랙티브 문제의 경우 출력을 하고, 언어에 따라 아래와 같은 명령어를 바로 다음에 적어 출력 버퍼를 flush해 줘야 한다. C: fflush(stdout); C++: fflush(stdout); 혹은 std::cout > n; string a[] = {"swimming", "bowling", "soccer"}; for (int i = 0; i < n; i++) // 그냥 swimming만 n번 출력해도 된다. cout