TIL 검색 결과
43 개의 검색 결과가 있습니다.
ProblemSolving

[BOJ] 1377_버블 소트

버블 소트 링크: https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 이 문제는 최종적으로 정렬이 되었을 때 몇 번째에서 정렬이 완료되었는지를 출력하는 것이 관건이다. 오름차순 정렬에서 버블소트는 가장 큰 수가 오른쪽으로 진행하게 된다. 이때, 한 번의 기회로 더 이상 횟수는 변하지 않는다. 하지만 작은 수는 왼쪽으로 이동을 수 없이 이동하게 될 것이다. 즉, 왼쪽으로 몇번 이동한지만 알 수 있다면 버블소트로 몇번만에 정렬이..

2021. 3. 14. 23:57
ProblemSolving

[BOJ] 1354_무한 수열 2

무한 수열 2 링크: https://www.acmicpc.net/problem/1354 1354번: 무한 수열 2 첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다. www.acmicpc.net n을 기준으로 하여 dp 배열을 생성하게 되면, 10^13의 크기를 생성할 수 없다. 따라서, 배열로 dp문제를 해결할 수 없다. map을 통해 필요한 index만 저장하고 꺼내서 사용하는 방식을 사용한다. 정답 코드 #include #include using namespace std; long long n, p, q, x, y; unordered_map dp; long long An(long long i) { if (i second; long long int a = An(i / p - x), b = A..

2021. 3. 13. 19:58
ProblemSolving

[BOJ] 1644_소수의 연속합

소수의 연속합 링크: https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 처음 소수부터 입력받은 수 n까지 각 case를 판단한다. 각 소수부터 다음의 소수들 합을 구하고 입력받은 수와 같은지 판단한다. 같은 경우만 count하고, 출력한다. 정답 코드 #include #include using namespace std; #define bigNum 4000001 bool primeNumber[bigNum]; vector primeList; void setPrime() { for (int i = 2; i < bigNum; i++) { primeNumber[i] = tr..

2021. 3. 8. 22:11
ProblemSolving

[BOJ] 1737_Pibonacci

Pibonacci 링크: https://www.acmicpc.net/problem/1737 1737번: Pibonacci 첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp top-down 방식으로 구현했다. Pibonacci는 다음의 규칙을 가진다. P[n] = 1 (0 ≤ n ≤ π) P[n] = P[n-1] + P[n-π] (그 외) 그리고 문제에서 다음의 힌트를 주었다. P[n-π] = P[n-π-1] + P[n-π-π] 이를 정리하면, P[n-π] = P[(n-1)-π] + P[n-2π] 이다. 배열로 n-π를 index로 사용하기에는 실수기 때문에 사용이 불가하다. 하지만, 위..

2021. 3. 6. 19:14
ProblemSolving

[BOJ] 1047_2로 몇 번 나누어질까

2로 몇 번 나누어질까 링크: https://www.acmicpc.net/problem/1047 1047번: 울타리 첫째 줄에 N이 주어진다. N은 2보다 크거나 같고, 40보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 나무가 심어져 있는 위치와 그 나무로 만들 수 있는 울타리의 길이가 순서대로 주어 www.acmicpc.net 1차 시도 실패 입력받은 사이 수를 2진법으로 변환 후 우측에서부터 체크한다. 가장 먼저 1이 나온 지점이 문제가 원하는 약수이다. 이를 더한다. 미해결 코드 #include #include using namespace std; #define maxNum 1000000000000000 long long unsigned int a, b; long long unsigne..

2021. 3. 5. 23:04
ProblemSolving

[BOJ] 1715_카드 정렬하기

카드 정렬하기 링크: https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 10 20 40의 카드 묶음들이 있을 때 최소 비교를 하기 위해서는 값이 오름차순으로 정렬되어 있어야 한다. 위 처럼 오름차순으로 정렬되어 있을 때 10 + 20 = 30이 또 다른 묶음이 되어 10과 20의 묶음을 제외한 나머지 카드 더미들과 비교를 수행해야한다. 10과 20은 이미 30번 수행을 했고, 이제 이 30개의 더미와 40개의 더미를 비교하면 70번..

2021. 3. 4. 21:58