본문 바로가기

Programming/BOJ Solutions

 (71)
[백준 1644번] 소수의 연속합 link : https://www.acmicpc.net/problem/1644 소수의 연속합 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB44861824133341.787%문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5..
[백준 11653번] 소인수분해 link : https://www.acmicpc.net/problem/11653 소인수분해 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB58593209258155.458%문제정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.입력첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.출력N의 인수를 한 줄에 하나씩 증가하는 순서대로 출력한다.예제 입력 1 복사72 예제 출력 1 복사2 2 2 3 3 예제 입력 2 복사3 예제 출력 2 복사3 예제 입력 3 복사6 예제 출력 3 복사2 3 예제 입력 4 복사2 예제 출력 4 복사2 예제 입력 5 복사9991 예제 출력 5 복사97 103 소인수분해 문제이다. 그냥 풀었다. 123456789101112131415161..
[백준 2960번] 에라토스테네스의 체 link : https://www.acmicpc.net/problem/2960 에라토스테네스의 체 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB51302590227252.027%문제에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 숫자 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 숫자를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) ..
[백준 1735번] 분수 합 link : https://www.acmicpc.net/problem/1735 분수 합 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB72653012255543.298%문제분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출..
[백준 1753번] 최단경로 link : https://www.acmicpc.net/problem/1753 최단경로 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB251867237339525.808%문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 ..
[백준 1922번] 네트워크 연결 link : https://www.acmicpc.net/problem/1922 네트워크 연결 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB74113952232651.563%문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 ..
[백준 1717번] 집합의 표현 link : https://www.acmicpc.net/problem/1717 집합의 표현 성공스페셜 저지시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB116123722246730.487%문제초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.입력첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친..
[백준 2003번] 수들의 합 2 link : https://www.acmicpc.net/problem/2003 수들의 합 2 성공시간 제한메모리 제한제출정답맞은 사람정답 비율0.5 초128 MB63532972221251.586%문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.출력첫째 줄에 경우의 수를 출력한다.예제 입력 1 복사4 2 1 1 1 1 예제 ..

티스토리툴바