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 1. Logic multiset 해설 1. 우선순위큐에 보석의 가치와 무게 순으로 넣는다. 2. 가방의 무게를 입력받아 multiset으로 넣는다. 3. multiset은 오름차순으로 정리되기 때문에 lower bound(O(logN))을 활용하여 보석의 무게와 같거나 더 큰 가방을 찾는다 vector 해설 1. 보석과 가방을 벡터에 입..
Algorithm
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 1. Logic 처음 생각은 긴 문자열부터 첫번째 짜리부터 순서대로 9, 8, 7 이렇게 큰 숫자부터 넣어주면 된다고 생각했지만 문자가 중복되게 나오는 경우의 수도 있기 때문에 고려를 해주어야 한다. 예를 들어 ABC BCA 같은 경우가 대표적인데, 이때는 A와 B중 어느 알파벳에 9를 할당해 줄 지 구해야 한다. 각 자릿수에 가능한 숫자를 구해보면 A=100 B=10 C=1 > 100A 1..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. Logic 항상 작은 값 2개를 선택해서 정렬해야 최소한으로 비교할 수 있게 된다. 우선순위 큐는 우선순위가 높은 값을 기준으로 즉 값이 큰 거부터 내림차순으로 정렬해 주는 자료구조이다. 우선순위 큐를 선언과 동시에 greater인자를 붙혀주게 되면 오름차순으로 정렬되기 때문에 문제를 풀기 적절한 자료구조이다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 1. Logic - 처음 시작 1은 무조건 양수로 시작한다고 이해하고 풀었다. 왜냐면 -1 -2 +3도 있지만 테케에 포함되지 않기 때문에 n = 9일 때를 생각해 보면 처음에 12가 들어오는 경우도 생기기 때문에 1을 먼저 박고 시작하지 않고 0일때를 분할하여 계산해주었다. 부분 문제 1. cnt == 0일때(처음 시작일 때) - 1을 더할지 - 12를 더할지 2. cnt == 0이 아닐때(처음 시작이 아닐때) - 한자리만 더할지 - 한자리만 뺄지..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. Logic - 문자 하나를 지날 때 마다 체크를 해서 다음 경로에서 이전에 어떤 문자를 지나왔는지를 확인해야하기 때문에 처음에는 자료구조 중 map을 사용해서 체크했다. 경로를 체크한 후 방문 처리한 계속 남아있게 되면 다른 경로를 진입할 때 continue 처리가 되기 때문에 DFS를 빠져나오면서 map에서 키값을 false로 돌려놔준다. 방문처리 하는 법 1. 자료구조 Map을 활..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. Logic 해당 문제는 메모리 제한이 4MB로 굉장히 작으므로 배열의 수를 최대한 줄이는 데 초점을 두고 풀이해야한다. 간단한 설명은 입력받은 수를 변수에 저장한 후 입력받은 수를 기준으로 위의 수를 서로 비교하여 크고 작은 수를 가져와서 현재의 배열에 저장하는 식으로 풀이한다. 코드를 보면 더 잘 이해가 갈 것이다. 2. Code #include using namespace std; int n; int ..
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 n + 1) ..
https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 1. Logic - 친구관계를 bfs를 돌면서 친구관계를 만들어준다. - Knapsack 알고리즘을 활용하여 사탕을 뺏을 수 있는 가치합의 최대값을 구해준다. 2. Code #include using namespace std; int n, m, k; vector vec[30001]; bool vis[30001];..
https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어 www.acmicpc.net 1. Logic 1. 최적경로 즉 시작부터 목적지까지 최단거리로 가는 경우가 있는지를 먼저 파악하기 위해 BFS통해 최단거리를 확인해놓는다. 2. 벨만포드를 돌면서 최단경로를 확인하고 v번을 돌면서 마지막 사이클에서 음의 사이클을 확인한다. 3. 벨만 포드 알고리즘을 돌면서 최단경로를 갱신할 때에만 주의 해야 할 사항 음의 사이클이 있다고 무조건 -1을 반환하는게 아니..
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 1. Logic - 해당 문제에서 시간이 거꾸로 가는 경로인 웜홀이 존재한다고 하였다. 이건 음수 간선을 나타내는 말이기 때문에 그래프 최단거리 알고리즘 중에서 음수가중치가 있을 때 사용할 수 있는 방법인 벨만-포드 알고리즘을 사용해서 풀이할 수 있다. 원래 벨만 포드 알고리즘은 V(노드의 갯수)-1만큼 순회하며 모든 간선을 확인하며 최단거리를 구하는 방법이다. 이 문제에서는 음수싸이..
