https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 입력조건이 1000000까지인 걸로 보아 2중 for문으로 접근하면 시간 초과가 날 것으로 예상할 수 있고, 스택으로 접근하였습니다. 수열을 탐색하면서 현재 원소가 이전의 원소보다 작을 때 까지 수열의 index를 스택에 push 하고, 현재 원소가 수열[스택의 top 원소값]보다 크게 될 경우 stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주면 됩니다. 또한 스택의 원소를..
Koala - 11기
Problem Solution N과 K를 입력받고 1부터 N까지의 숫자를 큐에 순서대로 넣는다. 큐가 빌 때까지 다음 과정을 반복한다. (먼저 현재 큐의 맨 앞에 있는 숫자를 K-1번 큐의 맨 뒤로 보낸다. 그 다음 큐의 맨앞에 있는 숫자를 출력하고 제거한다. 그리고 큐가 비어있지 않으면 쉼표와 공백을 출력한다.) 마지막으로 요세푸스 순열을 출력한다. Answer #include #include using namespace std; int main() { int N, K; cin >> N >> K; queue q; for (int i = 1; i
문제: 5533번: 유니크 (acmicpc.net) 5533번: 유니크 첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다. www.acmicpc.net 코드 코드 설명 먼저, 전역변수로 이중배열인 point와 포인트 값을 계산한 배열인 total을 선언해주었다. 그 후, 메인함수에서 N의 값을 입력 받은 후, for문을 이용하여 제출한 포인트 수를 입력 받아준다. 총 3게임을 진행하므로 먼저 3번을 반복시켜 준 다음에, for문을 이용하여 돌아가면서 각 자리수에 중복된 값이 있는지 확인 한다. 만일 중복된 값이 하나도 없으면 임의로 설정한 변수 cnt의 값은 0이 될 것이므로 cnt..
문제 https://www.acmicpc.net/problem/26042 26042번: 식당 입구 대기 줄 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 빈칸을 www.acmicpc.net Algorithm 뒤에서 부터 줄을 서고, 앞에서 부터 식사를 시작하러 들어가므로 큐를 사용하면 되는 문제이다. 줄에 서있는 사람이 최대가 될때, 마지막에 대기중인 학생의 번호를 찾으면 되는데, 이때 줄에 서있는 사람이 최대가 되는경우가 여러가지일 경우 마지막에 대기중인 학생의 번호가 최소가 되는 경우를 출력해야 한다. 줄을 큐를 이용하여 구현을 하면 된다고 생각했고, 2단계로 코드..
https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net # 문제 설명 - N*N의 표에 수가 채워져 있다. 모든 수는 자신의 한 칸 위에 있는 수보다 크다. - 이러한 표가 주어졌을 때 N번째 큰 수를 출력한다. - 1 n; for (int i = 0; i > x; pq.push(-x); if (pq.size() > n) pq.pop(); } cout
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 www.acmicpc.net 정답 코드 import sys si = sys.stdin.readline N = int(si()) graph = [] for i in range(N): tmp = list(map(int, si().split())) graph.append(tmp) # x, y 에따라 가능한 d1, d2의 조합 모두 체크 case_list = [] for d1 in range(1, N): for d2 in range(1..
문제 링크 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 코드 import heapq input = __import__('sys').stdin.readline for _ in range(int(input())): n = int(input()) visited = [False for _ in range(n)] max_heap, min_heap = [],[] for i in range(n): command = input() if command...
문제 링크 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 코드 from bisect import bisect_left input = __import__('sys').stdin.readline m,n,l = map(int,input().split()) people = sorted(list(map(int,input().split()))) cnt = 0 for _ in range(n): x,y = map(int,input().split()) if ..
https://www.acmicpc.net/problem/11179 11179번: 2진수 뒤집기 희연이는 스웨덴으로 이사하여 현재 학교를 다니고 있다. 1학년 교육과정은 중국에서 배웠고, 스웨덴과 중국 두 나라의 교육과정은 완전히 다르다. 희연이는 수학을 좋아한다. 하지만 지금은. www.acmicpc.net 문제해석 진접변환을 구현하여 2진법으로 바꾼후 그 수를 뒤집어 표현하는 문제이다. 코드 D = dict() result = list() for i in range(36): if i < 10: D[i] = str(i) else: D[i] = chr(55 + i) N = int(input()) while True: if N == 0: break x = N % 2 result.append(D[x]) N ..
https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 문제 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다. 진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다. 예를 들어, 위..
https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(12}를 써서 출력하도록 하였다.
풀이 최소 금액 K의 범위를 생각해봅시다. K는 각 날짜마다 필요한 금액보다는 크거나 같아야 합니다. 즉, K는 1부터 N * 최대 사용 금액 사이의 값일 수 있다. 이분 탐색을 이용하여 가능한 K 값을 찾습니다. 이때, 이분 탐색의 중간값(mid)을 사용하여 K를 검사한다. 주어진 N일 동안 각 날짜별로 사용할 금액을 순회하면서 현재 인출 가능한 금액(mid)로 사용할 수 있는지 확인한다. 만약 mid로 사용할 수 없는 날이 나온다면, 인출 횟수를 늘려야한다. 만약 인출 횟수가 M 이하라면, 가능한 K값 중 작은 범위에서 다시 탐색. 그렇지 않다면, K값을 더 큰 범위에서 탐색한다. 위를 반복하여 최소금액 K를 찾으면 된다. 코드 #include #include #include using namespa..
