어흥

문제 링크: www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사 www.acmicpc.net 1. 주의할 점 - 4차 배열을 사용하여 해당 지점에(y,x) 직전에 어떤 방향으로 도착했으며(dir), 현재까지 배달을 완료한 장소(del: 단, 장소를 구분해야 하므로 한곳: +1, 다른곳: +2) -> 비트마스킹이라고 생각하면 된다 - 구조체를 사용하여 현재 위치, 방향, 현재까지 배달을 완료한 장소, 현재까지의 이동거리를 저장한다 2. 구현 - 배달을 해야하는 장소(C)를 Deliver 벡터에 저장한다 ..

문제 링크: www.acmicpc.net/problem/11451 11451번: 팩맨 각 테스트 케이스에 대해서 정답을 한 줄에 출력한다. 만약 가능할 경우, 팩맨을 조작해야 하는 최소 횟수를 출력한 후, 그 다음에 조작해야 하는 방향을 순서대로 {N, E, S, W}를 사용하여 출력한�� www.acmicpc.net 1. 주의할 점 - 경로를 기억해야 한다 - BFS를 통해 진행하며, 팩맨 2가지의 위치를 한번에 저장하고 있는 구조체를 사용한다 - "귀신과 부딪힌다 -> 라이프가 1 깍인다" : 이 문구가 의미하는 것은? - "두 번째 팩맨" -> 이 문제와 상관이 없다. 불충분한 조건 or 낚시를 하다 만것 2. 구현 - "귀신과 부딪힌다 -> 라이프가 1 깍인다" : 이 문구는 낚시다. 귀신과 부딪..

문제 링크: www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 1. 주의할 점 - i번째 곡은 p-v[i] or p+v[i]여야 한다(범위가 아니다) - 최악의 경우 2^100 -> TLE 발생 2. 구현 - DFS나 그리디로 구현하면 TLE가 발생할 수도 있다 -> DP로 해결 - N과 M의 범위가 작다 -> 2차 배열을 이용해도 풀 수 있다 - DP[i번째 곡을][이 값으로 연주할 수 있다]: True or False ..

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

문제 링크: www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 1. 주의할 점 - EOF를 입력받을 때까지 입력받도록 한다 - 소숫점 아래 4번째 숫자까지만 받는다 2. 구현 - while(getline(cin, str)) 을 통해 EOF를 입력받기 전까지 종의 이름을 입력 받는다 - Map을 통해 각 종이 몇 번 입력 받았는지 계산한다 - 각 종이 입력 받은 백분율을 소수점 4째 자리까지 출력하도록 한다 #include #include #inclu..

문제 링크: 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/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 1. 주의할 점 - 메모리 제한이 작다. 메모리를 최대한 적게 쓰도록 한다 - Map을 1개 사용하고, 이분탐색을 통해 답을 유추한다 2. 구현 - A배열과 B배열을 입력받은 후, A배열에서 만들 수 있는 부분 배열을 Ma Map에 저장한다(숫자, 해당 숫자를 만들 수 있는 개수) - B배열의 부분 배열을 구할 때마다 Ma..

문제 링크: 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 : 기존배열에서 한바퀴 더 돌아서 ..