어흥

문제 링크: www.acmicpc.net/problem/2886 2886번: 자리 전쟁 R x C의 형태를 지닌 전차 안에는 의자와 사람들의 정보들이 주어진다. 사람들은 다리가 아픈 것을 매우 싫어하기 때문에 빈 의자가 보이면 무조건 앉으려고 한다. 하지만 나보다 의자에 가까이 www.acmicpc.net 1. 주의할 점 - 우선순위큐를 사용하여 정렬을 한다(거리의 오름차순으로) 2. 구현 - 입력받을 때, 사람과 의자의 정보를 기억해놓는다 - 사람들과 의자사이의 거리를 구하여 구조체 형식(사람 번호, 의자 번호, 거리)으로 저장한 값을 우선순위큐에 담는다 - 우선순위큐에서 거리가 같으며, 아직 해당 사람이 의자에 앉지 않았고, 의자 또한 비어있다면 V 벡터에 의자 번호를 담는다. 동시에 사람이 의자를 ..

문제 링크: www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 1. 주의할 점 - DFS + 메모아이징을 통해 구현하거나 글쓴이처럼 빙글빙글 돌아가게 풀지 않으면 TLE가 날 문제일것 같다 (N Transfer 큐에 저장 - find_dup() 함수를 통해 1번 역에서 시작해서 BFS 과정을 거쳐서 방문이 겹치는 지점을 구해서 Start에 저장한다 -> Start는 무조건 순환선에 속하기 때문에 구했다 - find_cycle() 함수..

문제 링크: www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마� www.acmicpc.net 1. 주의할 점 - N과 M이 같을때의 조건을 잘 세운다 - 최대 몇개를 확인하면 되는지 식을 잘 세운다 - While문 안에 For문을 이용하여 Sum을 계산하지 않는다 -> 두 포인터를 활용한다 2. 구현 - 입력받을 배열의 크기를 2배로 하여 N + M -1개의 배열에서 연속된 M개씩 고르도록 한다 - While문을 몇번 반복할것인지 Len을 구해야 한다. Len : 기존배열에서 한바퀴 더 돌아서 ..

문제 링크: www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 1. 주의할 점 - 최대 4*4이므로, 브루트포스 알고리즘을 사용한다 - 사용한 숫자처리를 제대로 하면 된다 2. 구현 - 배열을 입력받은 후, 왼쪽위 원소부터 브루트포스를 수행한다 - 브루트포스는 다음과 같은 순서로 진행된다. 해당 원소만 포함, 해당 원소포함 + 아래숫자들 포함, 해당 원소포함 + 오른쪽 숫자들 포함 - 단, 위의 기준은 항상 추가할 숫자가 방문처리되어 있지 않다는 가정하에 진..

문제 링크: https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 새로운 게임 2 풀이: https://imnotabear.tistory.com/214 [백준 17837] 새로운 게임 2 (C++) 문제 링크: https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행 imnotab..

문제 링크: https://www.acmicpc.net/problem/6416 6416번: 트리인가? 문제 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 �� www.acmicpc.net 1. 주의할 점 - 매 TC마다 Case를 1씩 증가시킨다 - 매 TC마다 벡터와 배열들을 초기화한다 - Root가 2개 이상 있는지, 없는지, 부모가 2개 이상인지, Root에서 모든 Node까지 도달 가능하지 전부 확인한다 - 0 0 또한 빈 트리로, 트리라고 출력해야 한다 2. 구현 - 입력받는 모든 Node들을 Set에 넣으며, 간선의 정보는 V[부모]에 자식에 대한 정보를 넣..

문제 링크: https://www.acmicpc.net/problem/3671 3671번: 산업 스파이의 편지 문제 안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요. 저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매�� www.acmicpc.net 1. 주의할 점 - 소수인 수를 미리 구해놓는다 - 매 TC마다 벡터들을 초기화한다 2. 구현 - 에라토스테네스의 체를 이용하여 소수면 Num[] 배열 자기자신을 입력한다 - 1~입력받은 수의 자리수 까지 DFS를 수행하며 구한 수가 소수라면 Set에 넣는다 #define MAX 10000000 #include #include #include #include #include #i..

문제 링크: https://www.acmicpc.net/problem/3967 3967번: 매직 스타 문제 매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다. 매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26� www.acmicpc.net 1. 주의할 점 - 마지막에 모든 경로의 합을 구하면 TLE 발생한다. 특정 지점마다 검사해줘야 한다 2. 구현 - Check[] 배열을 전부 -1로 초기화한다 - Check[] 배열을 통해 해당 번호가 현재 사용중이라고 표시한다 - Test[][] 배열을 통해 어떤 경로에 위치한 숫자를 계산해야 하는지 표시한다 - DFS()를 수행하며 Idx가 5,8,11,12일때 특정 ..