나그네

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 정점까지 가..

1753번: 최단경로 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 한 정점에서 다른 모든 정점까지 가는 최단 경로, 즉 최소 비용을 구하면 되는 문제다. 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘과 벨만포드 알고리즘이 있는데 이 문제에선 음의 가중치가 없기 때문에 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대한 설명은 아래 링크를 참고하길 바란다. [다익스트라 알고..

2579번: 계단 오르기 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 계단은 1칸 또는 2칸 이동가능하며 연속된 3개의 계단을 오를 수는 없다. 그리고 마지막 계단은 반드시 밟아야 한다. 얻을 수 있는 포인트의 최댓값을 구하는 문제. dp로 해결가능하다. dp[i]는 i번째 계단까지 가는 경우의 포인트의 최댓값이며 v[i]는 i번째 계단을 밟았을 때 얻는 포인트다. 1번째 계단까지의 최댓값은 dp[1] = v[1] 이다. 2번째 계단까지 가는..

4839번: 소진법 문제 https://www.acmicpc.net/problem/4839 4839번: 소진법 각 테스트 케이스에 대해서, 입력으로 주어진 수, 공백, 등호, 공백을 출력하고 문제 설명에 나온 것 같이 소진법으로 나타내 출력한다. www.acmicpc.net 풀이 소수의 곱을 이용하는 문제. 다만 수의 범위가 int 범위 안이기 때문에 29까지 곱하게 되면 범위를 벗어나서 23까지의 곱만 구하면 된다. 그래서 누적곱(?) 배열을 만들어줬다. 가장 큰 누적곱부터 비교하며 N이 누적곱보다 같거나 크다면 N을 누적곱으로 나눈 몫과 누적곱까지의 소수 곱을 출력 형식에 맞는 문자열 형태로 만들어 배열에 추가해 줬다. 그리고 N을 누적곱으로 나눈 나머지로 업데이트해 준다. 만약 누적곱 배열을 모두 ..

6500번: 랜덤 숫자 만들기 문제 https://www.acmicpc.net/problem/6500 6500번: 랜덤 숫자 만들기 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, a0을 포함하고 있다. (0 < a0 < 10000) 숫자가 네 자리가 아닌 경우에는, 앞에 0을 추가해 네 자리로 만들어져 있다. www.acmicpc.net 풀이 a0을 입력받고 a0 * a0을 앞에 0을 추가해 8자리 숫자로 바꿔준 다음 가운데 4자리를 a1으로 한다. 이를 반복해 가며 가능한 ai의 수를 구하는 문제. 숫자 N을 입력받고 N*N의 가운데 4자리를 다시 N으로 하며 모든 N을 계속 배열에 넣었다. 그러다 N이 이미 배열 안에 있을 경우 반복문을 탈출한다. 배열의 크기를 출..

1759번: 암호 만들기 문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 C개의 문자를 입력받아 길이가 L인 문자열을 구하는 문제다. 단, 문자열의 문자는 오름차순이어야 하며 모음이 최소 한 개, 자음이 최소 2개 포함하고 있어야 한다. 가능한 모든 문자열을 사전순으로 출력하는 문제. 백트래킹으로 풀었다. 문자열의 문자가 오름차순이어야 하므로 입력받은 문자들을 정렬해 주었다. 길이를 cnt로 두어 dfs 함수를 구현해 주었다. cnt ==..

26082번: WARBOY 문제 https://www.acmicpc.net/problem/26082 26082번: WARBOY 첫째 줄에 세 양의 정수 $A$, $B$, $C$($1 \le A, B, C \le 1\,000$)가 공백으로 구분되어 주어진다. $\mathbf{\mathit{B}}$는 항상 $\mathbf{\mathit{A}}$의 배수이다. www.acmicpc.net 풀이 경쟁사 제품의 가격 대비 성능을 구한 후 3배한 다음 WARBOY의 가격을 곱한 값을 출력한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int a, b, c; cin >> a >> b >> c; cout

9213번: 꽤 좋은 수 문제 https://www.acmicpc.net/problem/9213 9213번: 꽤 좋은 수 완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수이다. 예를 들어, 6의 약수는 1, 2, 3인데 1+2+3은 6이기 때문에 완전수이고, 28도 1+2+4+7+14 = 28이기 때문에 완전수이다. 어떤 자연 www.acmicpc.net 풀이 자신을 제외한 약수의 합과 자신의 차가 어떠한 수 이하이면 꽤 좋은 수다. 범위 내 꽤 좋은 수의 개수를 구하는 문제. 모든 수에 대해 일일이 약수를 구해 더하면 시간초과가 난다. 그래서 에라토스테네스의 채를 이용해야 한다. i=1부터 100만까지 1씩 증가하며, j=i*2부터 100만까지 i씩 증가하며 j 인덱스의 배열에 i 만큼..

1958번: LCS 3 문제 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 풀이 9251번 LCS의 확장 버전이다. 아래 문제와 다른 점은 문자열 두개가 아닌 세 개를 비교하는 문제다. https://khyunx.tistory.com/57 [백준 / BOJ] C++ 9251 LCS 9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통..

9252번: LCS 2 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 9251번 LCS의 확장 버전이다. LCS의 길이를 구하는 풀이는 아래 링크를 참고하길 바란다. https://khyunx.tistory.com/57 [백준 / BOJ] C++ 9251 LCS 9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Lon..