나그네

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 문제 https://www.acmicpc.net/problem/24263 24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 n회 반복되는 for문을 수행합니다. for문 안의 코드1은 n번 수행됩니다. 따라서 코드1의 수행 횟수는 입력받은 n과 같은 값을, 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 1입니다. 코드 #include using name..

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 문제 https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 항상 1번만 return 합니다. 따라서 수행 횟수는 1, 최고차항의 차수는 0입니다. 코드 #include using namespace std; int main() { int a; cin >> a; cout

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 풀이 각 난이도 별로 문제를 푸는 데 걸리는 시간을 저장하고 오름차순으로 정렬한다. 각 난이도별로 풀어야하는 문제의 수만큼 앞에서부터 고르면 된다. 이 문제에서는 문제를 푸는 데 필요한 시간을 최소화하고 휴식시간도 최소화해야한다. 휴식..