대회 링크 https://codeforces.com/contest/1804 A. Lame King https://codeforces.com/contest/1804/problem/A 문제 풀이 킹이 (0, 0)에 위치할 때, 도착해야 하는 목적지 (a, b)까지 도착할 때 이동 횟수의 최솟값을 출력하는 문제 킹이 할 수 있는 행동은 대각선을 제외한 인접한 구역에 이동하는 것과 이동을 멈출 수 있다. 킹은 같은 행동을 연속으로 하지 못한다. 이를 바탕으로 해결 방법은 다음과 같다. (0, 0)에서 a, b의 절댓값의 최소 값(min(abs(a), abs(b)))의 위치로 먼저 이동한다. 대각선으로 이동하는 것이므로 이동 횟수는 2 * min(abs(a), abs(b))이다. 남은 거리가 있는 경우는 해당 구..
대회 링크 https://codeforces.com/contest/1802 A. Likes https://codeforces.com/contest/1802/problem/A 문제 풀이 주어진 배열을 이용해 가장 큰 배열과 가장 작은 배열을 출력하는 문제 양수가 있는 배열인 arr와 음수가 있는 배열인 marr를 구분한다. max_arr는 1부터 max(arr)까지 한 다음 감소하는 형태로 배열을 만들면 된다. min_arr는 arr에서 하나, m_arr에서 하나씩 먼저 만들어 두고 남은 arr로 배열을 만들면 된다. 제출 코드 # 2023/03/09 Implementation # https://codeforces.com/contest/1802/problem/A for _ in range(int(input..
문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀이 가로 위치, 세로 위치, 방향, 세대의 정보(y, x, d, g)를 입력받고 드래곤 커브를 만든 후 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력해야 하는 문제 드래곤 커브를 만들려면 현재 위치에서 이미 만들어진 드래곤 커브의 정보(total_dr[::-1])를 가지고 와야 된다. 해당 정보에 대해서 이미 진행했던 방향에서 시계 방향으로 90도 회전..
문제 https://www.acmicpc.net/problem/27738 27738번: 연산자 파티 해당 예제는 서브태스크 1에는 주어지지 않음을 유의하시오. www.acmicpc.net 풀이 N과 A, B, C, D, E, F가 입력값으로 주어지고, 초기값이 0인 X가 i가 1부터 N까지 1씩 증가하는데, 이때 i가 A - F의 배수일 때 해당하는 X 값에 해당 연산을 수행하여 정답 X값을 출력하는 문제 1부터 N + 1까지 반복문을 돌려 해당하는 연산을 수행하면 된다고 생각하지만 N이 최대 10**12까지 반복문을 수행해야 하므로 턱없이 부족하다. 그렇다면 소요 시간을 줄일 수 있는 방법을 생각해야 하는데 그 해답은 아래 연산 수행 방법에 있다. i가 A의 배수인 경우 X = X + i연산을 수행한다..
문제 https://www.acmicpc.net/problem/27737 27737번: 버섯 농장 첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다. 버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸 www.acmicpc.net 풀이 N * N 칸으로 이루어진 나무판에 버섯 농사를 지을 때, 가지고 있는 버섯 포자를 사용해 농사가 가능한 경우와 불가능한 경우에 따른 정답을 출력하는 문제 시작할 때 M개의 포자를 가지고 있고, 이 포자를 심을 수 있는 공간에 심는다면 해당 구역부터 최대 K만큼 퍼져나갈 수 있다. 주의할 점은 버섯 포자를 하나라도 사용해야 한다는 점이므로 이를 감안하고 문제를 풀도..
문제 https://www.acmicpc.net/problem/27736 27736번: 찬반투표 투표가 통과되었으면 APPROVED, 통과되지 않았으면 REJECTED, 무효 처리되었으면 INVALID를 출력한다. www.acmicpc.net 풀이 모든 재학생이 투표를 했을 때, 찬성이 많은 경우, 반대가 많은 경우, 기권이 많은 경우에 따른 정답을 출력하는 문제 찬성이 많은 경우와 반대가 많은 경우는 서로를 비교하여 정답을 출력하면 된다. 기권이 많은 경우는 기권표의 수가 N의 절반보다 큰 경우 투표는 무효 처리된다. 제출 코드 # 2023/03/11 구현 # https://www.acmicpc.net/problem/27736 N = int(input()) arr = list(map(int,input(..
문제 https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 풀이 백곰 엘버트를 위해 적절한 위치에 있을 때, 얼음들의 합의 최댓값을 구하는 문제 현재 위치에서 K만큼의 영역이 있다고 생각하고 진행을 한다.(슬라이딩 윈도우) 영역에 들어온 경우 해당 값을 더한다. 영역에 벗어난 경우 해당 값을 뺀다. 계산하는 과정 중 나왔던 가장 큰 값을 반환하고 출력한다. 중복되는 값이 없으므로 check 리스트는 사실상 없어도 된다. 전체 배열을 생성한 뒤 해당 좌표의 얼음 값을 빼고 ..
문제 https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 풀이 남자와 여자가 주어진 조건에 맞게 쌍을 이룰 때 그 최댓값을 구하는 문제 키가 양수인 경우 성별이 같지 않고 자신보다 큰 성별과 짝을 이루고자 하는 것이고, 키가 음수인 경우 성별이 같지 않고 자신보다 작은 성별과 짝을 이루려고 하는 것이다. 남자 배열의 양수와 음수를 분류하고 여자 배열의 양수와 음수를 분류한다. (양수로 값을 저장) 양수인 남자와 음수인 여자와 쌍의 여부를 탐색하..
