나그네

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..

9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 입력된 두 문자열을 비교하면서 LCS(최장 공통 부분 수열)의 길이를 찾는 문제. 가능한 모든 경우의 수를 확인하면 시간초과가 나기 때문에 dp를 이용해 풀어야 한다. 예제를 통해 설명을 해보자. 비교하는 두 문자열은 "ACAYKP"와 "CAPCAK"다. 최장 공통 부분 수열은 "ACAK"로 길이는 4다. 0 A C A Y..

1269번: 대칭 차집합 문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 풀이 C++ STL인 map을 사용하여 쉽게 풀 수 있다. A, B 집합을 입력받고 A집합에 없는 B집합의 원소의 수, B집합에 없는 A집합의 원소의 수를 구해 더한다. 코드 #include using namespace std; int main() { // 입력 int n, m, cnt = 0, x; cin >> n >> m; map A, B; for (int ..

1267번: 핸드폰 요금 문제 https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금 동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 30초 미만이거나 60초 미만이어도 요금이 나오므로 나눈 후 1을 더하고 요금을 곱하면 된다. 코드 #include using namespace std; int main() { int n, time, y = 0, m = 0; cin >> n; for (int i = 0; i > time; y += 10 * (time / 30 + 1); m..

14622번: 소수 게임 문제 https://www.acmicpc.net/problem/14622 14622번: 소수 게임 인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있 www.acmicpc.net 풀이 에라토스테네스의 체로 미리 500만 이하의 소수를 구해놓은 다음, 입력 범위를 주의하며 차례대로 조건에 따라 구현하면 되는 문제다. 입력받은 수에 따라 조건을 나누어보겠다. 1. 이미 등장한 소수인 경우 이미 등장한 소수인 경우엔 자신이 -1000점을 얻는다. 2. 처음 등장하는 소수인 경우 처음 등장한 소수인 경우엔 해당 소수를 방문처리하고 정렬이 오름차순인 우선순위..

14490번: 백대열 문제 https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 풀이 N, M을 입력받아 최대한 약분하여 출력하는 문제다. 당연 최대공약수로 나누어주면 그만이다. 입력이 100:10 같은 형태로 입력되기 때문에 cin이 아닌 scanf로 입력을 받았다. 코드 #include using namespace std; // 유클리드 호제법 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n, m; scanf("%d:%d", &n, &m); int g = gcd(n, m..