본문 바로가기

Programming455

[C/C++] 백준 #2331 반복수열(구현) #2331 반복수열 문제는 단순하게 구현만하면 됩니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 이 문제에서 구현의 초점은 바로 자리수를 가져오는 것과 그것을 p제곱하는 것입니다. A란 숫자가 있으면, p값이 바뀌지 않는다면, 모든 자릿수를 p제곱한 후의 합은 항상 같은 숫자가 됩니다. 저는 개수를 세기 위해서 배열에 count를 하게 했습니다. 배열의 최대 개수는 9의 5제곱은 59049이므로 이것을 4개 더한 236196보다 크게 잡아주면 됩니다. 제가 구현한 소스입니다. //---------------------------.. 2023. 4. 26.
[C/C++] 백준 #2316 도시 왕복하기 2(포드-폴커슨 알고리즘) 도시를 디니면서 어떤 조건을 만족하는 문제들은 조건에 따라서 푸는 방법들이 다양합니다. NP-Hard 문제인 세일즈맨 문제와 같이 특정 알고리즘이 없는 문제도 있지만, #2316 문제와 같이 문제를 변행해서 기존의 알고리즘을 적용할 수 있는 문제도 있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 이 문제는, 1번 도시에서 2번 도시로 이동을 하는데, 한번 방문했던 도시는 다시 방문하지 않고, 몇번 왔다갔.. 2023. 4. 25.
[C/C++] 백준 #2312 수 복원하기(수학) 소인수 분해하는 것은 어렵지 않게 할 수는 있습니다. 물론 소수를 구해서 하면 더 좋겠지만, 소수를 별도로 구하지 않아도 소인수 분해를 할 수 있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2312 2312번: 수 복원하기 첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다. www.acmicpc.net 소인수 분해를 할 때에는 n의 숫자의 제곱근까지만 하면 됩니다. 예를 들어서 12를 소인수 분해하기 위해서는 2부터 시작합니다. 12의 제곱근은 3보다는 크고 4보다는 작겠죠. 즉, 3까지만 하면 됩니다. 하지만, 제 알고리즘은 그 전에 끝나게 됩니다. 12를 2로 계속 나누면, 2번 나눌 수 .. 2023. 4. 20.
[C/C++] 백준 #2302 극장 좌석(동적 계획법) #2302 극장 좌석 문제는 수학적인 원리를 이해하면 풀기 편합니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석은 일렬로 최대 40개까지 있을 수 있습니다. 이 중 몇개의 좌석은 이미 고정석으로 채워져 있을 때, 1부터 N까지의 숫자를 채우는 경우의 수를 구하는 문제입니다. 단, 모든 숫자는 자신의 자리 번호와 그 옆자리로 이동을 할 수 있지만, 고정석으로는 이동할 수 없습니다. 극장 자리는 아래와 같이 표시될 수 있습니.. 2023. 4. 20.
[C/C++] 백준 #2294 동전 2(동적 계획법) #2294 동전 문제도 #2293 동전 문제와 비섯합니다. 단, 가치가 같은 동전이 주어질 수 있다는 것 뿐으로 크게 고려 대상은 아닙니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 참고할 수 있는 이전 문제 링크입니다. https://sdev.tistory.com/1333 [C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 .. 2023. 4. 20.
[C/C++] 백준 #2293 동전 1(동적 계획법) 동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 주어진 K원을 만들기 위해서는 동전의 종류를 먼저 조절해야 합니다. 서로 다른 동전의 종류가 n개가 있다면, 우리는 동적 계획법의 변수 \(d_{n, k}\)를 정의하도록 합니다. n개의 동전을 가지고 k 금액을 만드는 경우의 수로 정의토록 합니다. 이렇게 하면 다음과 갈은.. 2023. 4. 20.

티스토리툴바