나그네

27494번: 2023년은 검은 토끼의 해 문제 https://www.acmicpc.net/problem/27494 27494번: 2023년은 검은 토끼의 해 흑묘 복권의 티켓 수 $N$이 주어진다. $(1 \leq N \leq 10\,000\,000)$ www.acmicpc.net 풀이 2023부터 N까지 차례대로 문자열로 바꾸어 어느 한 부분에 차례대로 2, 0, 2, 3이 존재하는지 확인하면 되는 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, ans = 0; cin >> n; for (int i = 2023; i

4485번: 녹색 옷 입은 애가 젤다지? 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 2차원 배열에서 (0,0)에서 (N-1, N-1)까지 한 칸씩 이동하며 각 칸의 숫자의 합이 최소가 되도록 하는 문제다. 다익스트라 알고리즘을 2차원 배열로 만들어서 풀었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 2차원 배열에서의 BFS처럼 dy, dx 배열을 만들어..

18223번: 민준이와 마산 그리고 건우 문제 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 풀이 최단 경로 중에 민준이가 위치한 정점이 포함되는지 확인하는 문제다. 다익스트라 알고리즘으로 두 정점 간의 최단 경로를 구할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 건우가 위치한 P 정점이 최단 경로 위에 있다면, (시작점부터..

17396번: 백도어 문제 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 풀이 0번에서 N-1번까지 가는 최단 경로를 구하는 문제다. 몇 가지 예외만 처리해 주면 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 예외인 경우는 넥서스를 제외한 시야가 밝혀져 있는 정점은 지나갈 수 없다. 따라서 간선을 입력받을 때 해당 정점과 연결..

1963번: 소수 경로 문제 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 4자리 소수 A, B를 입력받고 A를 적절히 바꾸어 B를 만드는데 몇 번 만에 바꿀 수 있는지 구하는 문제다. 바꾸는 데는 규칙이 있다. 1. 한 번에 한 자리 수만 바꿀 수 있다. 2. 바뀐 수도 반드시 소수여야 한다. 소수인지 판단하기 위해 에라토스테네스의 체를 사용해 소수를 걸러준다. 그리고 bfs를 돌렸다. A를 방문처리하고 큐에 넣는다. 이때 큐는 pair를 원소..

2211번: 네트워크 복구 문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이 1번 정점의 슈퍼컴퓨터에서 모든 정점에 이어야 하므로 최소 시간에 연결이 돼야 하므로 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 문제에서 요구하는 것은 이어야 하는 간선의 수와 그 간선이다. 따라서 -1로 초기화되어 있는 prev 배열을 만..

10282번: 해킹 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 의존성이 있는 컴퓨터에 바이러스가 전염되는 시간과 몇 대의 컴퓨터가 감염되었는지 구하는 문제다. 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] !! 신경 쓸 점이 두 가지 있다. 1. 테스트 케이스가 여러 개이므로 배열과 변수 초기화에 신경 써야 한다. 2. a가 b에 의존하고 있..

5972번: 택배 배송 문제 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 양방향 그래프에서의 다익스트라 알고리즘을 사용하면 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int N, M; vector graph[50001]; vector dist(50001, INF), visit..

1427번: 소트인사이드 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 숫자의 각 자리 수를 내림차순으로 정렬하는 문제다. 숫자를 string 타입으로 입력받고 내림차순으로 정렬해주면 된다. 내림차순 정렬은 비교 연산자 위치에 greater()을 넣어주면 된다. 코드 #include using namespace std; int main() { string a; cin >> a; sort(a.begin(), a.end(), greater()); cout

1422번: 숫자의 신 문제 https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 풀이 K개의 수를 N번 사용해 가장 큰 수를 만드는 문제다. 단, 모든 수는 한 번은 이용해야 한다. 1. K개의 수 정렬 연결했을 때 가장 큰 수를 만들기 위해서 말 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경..