![]()
풀이 각 풍선의 값을 덱에 값, 풍선 번호 쌍으로 저장한다. 이떄 풍선번호는 1~N까지 순서로 진행된다. 현재 풍선의 값을 cur에 저장하고, 해당 풍선의 번호를 출력한다. 현재 풍선은 이미 터진 것으로 처리하고, 덱에서 제거한다. cur이 양수인 경우: cur-1만큼 덱의 앞부분을 뒤로 옮긴다. cur-1번만큼 이동 cur이 음수인 경우: -cur번만큼 덱의 뒷부분을 앞으로 옮긴다. cur번만큼 음수값으로 이동 풍선을 모두 터뜨린 후에는 풍선의 번호를 출력한다. 번호는 터뜨린 순서대로 출력된다. 코드 #include #include using namespace std; deque dq; int N; int main(void) { cin >> N; int num; for (int i = 0; i < N;..
![]()
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 ..
![]()
문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 초기 설정 0으로 이루어진 NXN 크기의 graph를 생성한다. 사과가 있는 위치는 1로 변경한다. 방향 변환 정보를 deque으로 저장한다. (li) x, y 위치 정보를 위해 리스트를 생성하고, 방향을 위한 d를 초기화한다. 뱀의 머리부터 꼬리까지 차지하고 있는 위치를 저장하기 위한 deque를 생성하고 시작 위치를 넣어준다. (dq) 반복 방향 변환 정보가 존재하고 time에 해당한다면 ..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 1. 문제풀이 대기줄에서 한 명씩만 설 수 있는 공간을 거쳐서 간식을 받을 수 있는 방법으로 구현하였다. 모든 사람들이 처음에 대기열에서 다른 대기 공간으로 간다. 다른 공간을 스택으로 구현하여, 순번에 맞는 사람이 대기열에 존재할 때까지 다른 공간에 일렬로 서게 된다. 해당 스택의 마지막으로 들어온 사람의 값이 간식을 받을 차례가 아닌 경우 문제 조건에 어긋나므로 Sad를 출력하고 종료하고, ..
문제 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque(enumerate(map(int, input().split()))) ans = [] cnt=0 while q: if cnt>=0: idx,paper=q.popleft() else: idx,paper=q..
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하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주면 됩니다. 또한 스택의 원소를..
![]()
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
![]()
문제 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/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/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 문제 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다. 진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다. 예를 들어, 위..
