어흥

문제 링크: www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1. 주의할 점 - 이분탐색 + 다익스트라를 이용하여 문제를 해결한다 2. 구현 - 2가지의 방법으로 풀었으며, 다익스트라는 우선순위큐를 활용하여 푸는 방법이 훨씬 빠르다 - Result의 값은 -1로 초기화한다(N번 컴퓨터까지 도달하지 못할 경우를 대비) - Dijkstra() 함수만 바뀐다 - 메인 함수에서 케이블선에 대한 정보를 받을 때, 케이블선의 최..

문제 링크: www.acmicpc.net/problem/6443 6443번: 애너그램 N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다. www.acmicpc.net 1. 주의할 점 - 문자열의 길이가 최대 몇인지 모른다 -> 배열을 이용해서 풀기 애매하다 - 문자열의 길이가 최대 몇인지 모르므로 Set을 사용하기 애매하다 -> TLE나 메모리초과가 날 수도 있다 2. 구현 - 그리디를 통해 접근한다 - 문자열을 입력받을 때, Sort 작업 수행과 Len을 설정한다 - DFS() 함수를 통해 idx가 문자열 길이-1일때 문자열을 출력한다 - For문을 통해 현재 바꾸려고 하는 위치의 문자와 다른 문자가 같은 숫자라면 ..

문제 링크: 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() 함수..