이번 문제는 투포인터를 개념을 적용해서 바로 풀 수 있었던 문제였던 것 같습니다. 에라토스테네스의 체를 통해서 MAXNUM까지의 소수를 구해주었습니다. 입력받은 n까지의 소수 개수 세고, 소수를 배열에 담아주었습니다. 투포인터 코드를 적용하여 마지막에 경우의 수를 출력해주었습니다. 소스코드 #include #define MAXNUM 4000000 using namespace std; bool check[MAXNUM]; int arr[MAXNUM]; int main(void) { int n; for (int i = 2; i n; int num=0; int idx=0; for (int i = 2; i = n) sum -= arr[lo++]; else if (hi == num) break; else sum +..
Koala - 4기
참고자료와 강의를 들으니 바로 풀리는 문제였다. 에라토스테네스의 체로 소수를 모두 구한 뒤 two pointer를 사용해 구하면 되는 문제였다. MAX 값을 4000000으로 고정 시킨 후 4000000까지의 소수를 구한 후 해당 소수들을 vector에 저장시켰다. 그 후 vector안의 값의 합이 입력 값과 같은지 two pointer를 사용해 확인한다. #include #include #include #include using namespace std; const int MAX = 4000000; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); vector prime; bool isPrime[MAX+1]; fill(isPrime+2, isPrime+..
문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이가 매우 직관적이어서 개인적으로 좋다고 생각했던 문제입니다. 코알라 투 포인터 강의영상 에서 나온 2003번 문제에 에라토스테네스의 체를 덧댄 버전입니다. 해결 방법은 정말 깔끔합니다. 1부터 N 사이에 있는 소수들의 배열(리스트)을 미리 만들어 두고, 해당 테이블에 대해 투 포인터 방법을 사용해 인덱스를 움직여가며 부분합이 N이 되는지 검사하기만 하면 됩니다. 저의 경우에는 소수들의 배열을 그냥 문제에서 주어진 범위인 4백만개로 초기화했지만, 그래도 시간 복잡도는 체를 만들 때 O(NlogN) +..
가희의 로그 N개의 로그 Q개의 임무 시작시간 - 종료시간 로그 레벨 lv 이상인 로그가 몇번 발생했는지 시작시각과 종료시간에 발생한 로그 포함 생각 문자열로 그대로 비교해보기 입력 받은 대로 파싱 진행 - : # 제거해서 문자열로 저장 처음에는 1 ≤ N ≤ 2×105 1 ≤ Q ≤ 2×105 이 조건을 생각하지 않고 마지막에 for문을 사용해 비교했다가 시간초과가 계속 생겼다. 이분 탐색을 사용한 후에도 시간초과가 나길래 혹시 몰라 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 를 추가해보니 바로 해결됐다. 다음 부턴 그냥 기본으로 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);를 박고 코드를 짜야겠..
백준에 제출을 할 경우 런타임 에러(Seg Fault)가 계속 뜨는데요. 찾아보니까 Seg fault 에러가 할당하지 않은 메모리 영역에 접근할 경우 뜨는 에러라고 하더라구요. 테스트 케이스를 이것저것 넣어봤을 때 결과는 제대로 나오는데 어떤 부분 때문에 SegFault 에러가 계속 뜨는지 잘 모르겠습니다.. #include #include #include #include using namespace std; vector vec[7]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; getchar(); for (int i = 0; i < n; i++) { string s, temp; getl..
입력값의 최대 범위가 4,000,000이므로 숫자 하나하나 소수 판정을 하였다가는 시간초과가 날 것이 분명하므로 에라토스테네스의 채를 이용해 입력받은 수 범위 이내의 소수들을 배열에 저장해놓고 그 값들과 포인터 두 개로 더했다 뺐다를 반복해주며 n과 같은 경우가 발생한 횟수를 기록해주기만 하면 되는 문제일 것입니다. prime=[1 for i in range(n+1)] # n까지 수의 범위 for i in range(2,int(n**0.5)+1): # 소수 판정을 위해 사용할 수의 범위 sqrt(n) if prime[i]==1: for j in range(i*2,n+1,i): # i 의 배수들 지워나가기 prime[j]=0 prime=[i for i in range(2,n+1) if prime[i]==1..
처음 문제를 읽고 든 생각은 탐색 문제라는 것이고 for문 2개로 하기에는 입력값이 너무 크므로 다른 방법을 사용해야 된다고 생각했습니다. 시간이 정렬되어 들어오고 중복된 값도 존재하는 것을 보고 이분 탐색을 써야겠다고 생각했습니다. 그리고 입력들어오는 형태 그대로 대소비교를 해도 괜찮은 형태로 들어오므로 그대로 사용하기로 결정했습니다.((2021-04-05 17:17:11end or arr[i][-1]
먼저 입력의 형태를 한눈에 봤을 때, 주어진 시간을 초 단위로 파싱하는 로직을 짜야겠다는 생각이 들어 파싱을 진행했습니다. 2 2 2021-04-05 17:17:11#1 2021-04-05 17:18:11#2 2021-04-05 17:17:11#2021-04-05 17:18:11#1 2021-04-05 17:18:11#2021-04-05 17:19:11#3 def parseYearToSecond(year): if year == 2000 or year == 2004 or year == 2008 or year == 2012 or year == 2016 or year == 2020: return year * 60 * 60 * 24 * 366 else: return year * 60 * 60 * 24 * 365..
힌트 1 더보기 약 21년의 시간을 초 단위로 나타내어 대소 비교를 할 수 있습니다. 힌트 2 더보기 로그에 대한 시간들이 순서대로 정렬되어 있을 때, 어떤 시간 A보다 크거나 같은 수가 처음 발견되는 위치는 O(logn) 시간에 찾을 수 있습니다. 힌트 3 더보기 종료 시각보다 큰 수가 처음 발견되는 위치 - 시작 시각보다 크거나 같은 수가 처음 발견되는 위치 번외 힌트 더보기 사실 문제처럼 연, 월, 일, 시, 분, 초로 되어있는 로그는 숫자만 모두 모아두면 그 자체로 대소비교가 가능합니다. 예를 들어 2000-01-02 12:12:12 -> 20000102121212 , 2021-04-05 17:17:11 -> 20210405171711 이 부분은 long long 형으로 변환해도 되지만, 그냥 s..
1~1000 사이의 n입력받아 길이가 n인 배열을 입력받는다. 한 번에 이동할 수 있는 거리는 0~100 사이의 값이고 1부터 1000까지 최대 이동 횟수는 999회. 각 위치에 해당하는 최소 이동횟수를 저장시켜야 함 -> DP 문제일 것. 입력도 작고 이동 거리도 작으므로 그냥 BFS로 다 넣어서 풀어도 풀리긴 할 것? bfs 풀이 쓸데없는 곳까지 굳이 탐색하여 시간효율도 별로고 배열도 써서 메모리 효율도 별로일 듯.. dp로 예상됨. # 뒤로 가는거 없음. # bfs? 로 풀 수 있을 듯? import sys from collections import deque input=sys.stdin.readline n=int(input()) arr=list(map(int,input().split())) vis..
생각 정리 1. dp[i]를 점프해야 하는 최소 횟수로 정의 2. 횟수가 제일 많은 경우는 n이 1000이고, 입력된 숫자가 모두 1일 때라고 생각(-1이 나오지 않는 범위에서) -> 시간 초과가 나지 않는다고 생각. 3. 점프해야 하는 최소 횟수를 정의하라고 했기 때문에 dp의 모든 인덱스를 아주 큰 수로 초기화 4. a[i]에 입력된 수만큼 떨어진 곳 이하에 점프해야 하는 최소 횟수를 대입하고, 미리 저장되어 있는 최소 횟수와 그 이후 들어온 횟수를 비교해서 min 값을 저장 5. dp[n]이 987654321로 남아있다면 도달하지 못한 것이므로 -1을 출력 소스코드 #include #include #include #define MAXNUM 987654321 using namespace std; in..
문제 링크 : https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net DP 문제입니다. 저는 원체 DP에 익숙하질 않아 상태표를 그려가면서 규칙을 파악하려 했는데요, 그 결과 다음과 같은 흐름을 잡을 수 있었습니다. 10 1 2 0 1 3 2 1 5 4 2 위의 기본 테스트케이스를 예로 들어 설명해보겠습니다. 입력받은 값들이 arr 라는 배열에 담겼다 하고, 해당 배열의 순회를 시작합니다. (1번 for문) 조건에 따르면 배열의 요소에 해당..
