나그네

16496번: 큰 수 만들기 문제 https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 풀이 N개의 수를 이어붙여 가장 큰 수를 만들기 위해서 문자 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경우엔 110이 더 크기 때문에 위치가 바뀌지 않는다. 출력 조건이 하나 더 있는데 만약 답이..

1330번: 두 수 비교하기 문제 https://www.acmicpc.net/problem/1330 1330번: 두 수 비교하기 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. www.acmicpc.net 풀이 두 수 a, b를 입력받고 a가 크면 >를, b가 크면 > a >> b; if (a > b) { cout

1316번: 그룹 단어 체커 문제 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 풀이 문자열 내에서 같은 문자는 연속해서만 나타나면 그룹 단어다. 따라서 i번째 문자와 i+1번째 문자가 다른 경우에만 이후에 i번째 문자와 같은 문자가 있는지 확인해주면 된다. 코드 #include using namespace std; int main() { int n, ans = 0; cin >> n; for (int i = 0..

1292번: 쉽게 푸는 문제 문제 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 풀이 1 2 2 3 3 3 4 4 4 4 5 와 같이 1을 1번 2를 2번 3을 3번인 수열에서 a번째부터 b번째 수의 합을 구하는 문제다. cnt 변수를 하나 만들어주고 cnt 만큼 cnt를 배열에 추가하도록 했다. 배열 크기가 b를 넘지 않도록 하여 제한을 뒀다. 이후엔 합을 더하면 끝인 간단한 문제다. 코드 #include using namespace std; int main() ..

1202번: 보석 도둑 문제 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개의 보석만 담을 수 있다. 훔칠 수 있는 보석의 가격의 최댓값을 구하는 문제. 먼저 기본적인 틀은 최대 무게가 가방에 담을 수 있는 보석 중에 가격이 가장 큰 보석을 담는 것이다. 당연히 담을 수 있는 무게가 큰 ..

1932번: 정수 삼각형 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 삼각형의 가장 위에서 아래로 차례대로 더해 최댓값을 구하는 문제. dp를 사용해 풀었다. 삼각형의 어느 위치에서 합의 최댓값이 되려면 그 윗 층의 인접한 두 위치까지의 합 중 더 큰 곳에 해당 위치의 값을 더한 값이 된다. 이를 구현하면 끝인 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >>..

11779번: 최소비용 구하기 2 문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 최소비용 구하기(1916번) 문제에서 확장된 문제다. 풀이는 아래 링크 참고. https://khyunx.tistory.com/71 [백준 / BOJ] C++ 1916 최소비용 구하기 1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에..

1916번: 최소비용 구하기 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 다익스트라 알고리즘으로 쉽게 풀 수 있는 문제다. 다익스트라 설명은 아래 링크를 참고하면 된다. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int main() { ios::sync_with_stdio(false); cin.tie(NULL..

1504번: 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 정점 1에서 출발해 특정한 두 정점 v1, v2를 지나 정점 N에 도착하는 최단 거리를 출력하는 문제다. 다익스트라 알고리즘을 사용해 풀 수 있으며 양방향 그래프임을 기억하고 풀어야 하며 경로가 없는 경우 예외 처리 하는 게 힘들었다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자. [다익스트라 알..

1238번: 파티 문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 1부터 N까지 각 마을에 사는 학생이 X번째 마을에 갔다가 돌아오는 최단 거리가 가장 오래 걸리는 학생의 이동 거리를 구하는 문제다. 다익스트라 알고리즘을 이용하면 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 참고하자. [다익스트라 알고리즘 알아보기] 이 문제는 유향인 그래프이고 i 정점부터 출발해 X 정점까지 가..