본문 바로가기
728x90

분류 전체보기423

[python] 백준 12851 숨박꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해결 가장 빠르게 N에서 K로 가는 길을 찾으면 된다. 이 때는 BFS를 이용하는 것이 좋다. 이동 했는데 이미 방문한 적이 있으면 더 빠르게 이동 할 수 있는 방법이 존재하는 것이므로 pass한다. ways를 통해 이동할 수 있는 방법이 여러개면 여러개가 있다는 것을 value 값을 통해 더해주면서 이동할 수 있다. CODE from collection.. 2023. 11. 1.
[C++] 백준 17427 약수의 합 2 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 해결 시간으로 보았을 때 $O(n)$의 시간복잡도를 가져야한다. 그러기 위해서는 각각의 약수의 합을 구해서 더하는 방식으로 할 수 없다.(최소 $O(n\sqrt{n})$) 1부터 n까지 반복문 $i$을 돌릴 때 n을 $i$로 나누면 n까지 숫자중 $i$를 약수로 갖는 개수가 나온다. 따라서 $i$를 곱해주면 $i$를 약수로 갖는 것들.. 2023. 10. 31.
[C++] 백준 2637 장난감 조립 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제 해결 위상정렬 문제라는 것을 쉽게 알 수 있다. 가장 마지막에 완제품 n이 오므로 n부터 시작해서 앞에 제품들을 조사한다. CODE #include #include #include #include using namespace std; vector adj[101]; int in[101], cnt[101]; int main() { int n; cin >> n; int .. 2023. 10. 24.
[python] 백준 2659 십자카드 문제 https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 문제 해결 주어진 입력값을 가지고 시계수를 구하는 함수를 만든다. 그 방법은 맨 앞의 숫자를 맨 뒤로 옮겨가며 가장 최솟값이 나오는 수를 구하면 된다. 1111은 가장 작은 시계수인 것은 명백하다. x를 입력값을 십자모형의 카드에 넣어 얻은 시계수라고 하면 1111부터 x까지 시계수의 개수를 구하면 되는 문제이다. CODE import sys input = sys.stdin.readline def clock_num(n): .. 2023. 10. 18.
728x90