문제 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 풀이 남자와 여자가 주어진 조건에 맞게 쌍을 이룰 때 그 최댓값을 구하는 문제 키가 양수인 경우 성별이 같지 않고 자신보다 큰 성별과 짝을 이루고자 하는 것이고, 키가 음수인 경우 성별이 같지 않고 자신보다 작은 성별과 짝을 이루려고 하는 것이다. 남자 배열의 양수와 음수를 분류하고 여자 배열의 양수와 음수를 분류한다. (양수로 값을 저장) 양수인 남자와 음수인 여자와 쌍의 여부를 탐색하..
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 가장 효율적으로 보석을 훔치고 보석 가격의 최댓값을 출력하는 문제 가방 크기에 맞게 보석을 담는다. 담을 수 있는 보석이 있다면 가장 큰 값을 가진 보석을 담는다. 해결해야 하는 부분은 위와 같으며, 이를 우선순위큐(heap)를 이용하여 문제를 해결해 보았다. 주의해야 할 점 가방의 크기는 오름차순으로 정렬해야 한다. 왜냐하면..
문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 정수 A를 B로 주어진 연산을 이용해 만드는 문제 주어진 연산은 다음과 같다. 2를 곱한다 1을 수의 가장 오른쪽에 추가한다. 일단 B에서 A로 바꾸는 풀이로 문제를 해결했다. 첫 번째로 끝이 1이라면 제거해 본다. 두 번째로는 짝수인 경우 2로 나누어 본다. A로 바꾸는 데 성공한 경우 횟수를 출력한다. BFS로 풀 필요는 없고 다른 방법으로 풀 수 있는 문제이다. 제출 코드 # 2023/03/08 bfs # https://www.acmicpc.net/problem/16953 from collections i..
