거의 알고리즘 일기장

풀이방법 A : 1 + 2 + 4 + .. + 2^k-1의 축적합을 구해서 주어지는 수를 나눠주면 된다. 주의사항으로는 int의 범위값을 넘기때문에 담는 배열을 long long으로 만들어주면된다. 축적합은 30까지만 만들어주면 주어진 범위 넘으니 30까지만 만들어주자. #include #include #include using namespace std; long long aSum[31]; void ASumInit() { for (int i = 1; i num; solve(num); } return 0; } B : n%4 == 0이여야 조건중 하나인 배열의 1~n/2까지 누적합 *2 = 배열의 1~ n까지의 누적합이 성립한다. 이제 no는 문제가 없고 yes일때 list를 생각해면 나같은 경우에는 만약에..

https://codeforces.com/contest/1213 Dashboard - Codeforces Round #582 (Div. 3) - Codeforces codeforces.com 먼저 풀었던 a, b, c 번 부터 리뷰하고 이후 문제는 아직 풀이를 제대로 하지 못해 이후에 리뷰하겠다. 풀이방법 A. Chips Moving 칩을 옮겨서 같은 곳에 두는 방법중 최소의 수를 찾는 문제다. 먼저 조건을 잘보자. 잘 보면 홀수와 짝수인 개수를 세고 둘중에 작은 것의 개수를 구하는 문제라는 것을 알수있을것이다. 이후는 생략~ B. Bad Prices 이 문제는 지금 위치의 값보다 작은 값이 있는지 없는지 알아보는 문제이다. 별건 없고 역순으로 MIN값을 만들어 비교하면 개수를 세면 끝이다. C. Boo..

https://codeforces.com/contest/1213 Dashboard - Codeforces Round #582 (Div. 3) - Codeforces codeforces.com 코드포스 virtual 처음풀어봤는데 3문제밖에 못풀었다.. 1시간넘게 D번을 시간내에 푸는 방법을 찾지못했다. 그리고 문제 이해도 잘 못하겠어서 많이 힘들었다. 하다보면 늘겠지ㅠ 리뷰 하다간 오늘 밤샐것 같으니 걍 자야지 ㅎ

https://codeforces.com/problemset/problem/455/A Problem - 455A - Codeforces codeforces.com 풀이방법 ak를 선택시 ak-1, ak+1은 선택 못한다는것을 유의해서 점화식을 짜야한다. dp[i] = max( dp[i-1], dp[i-2] + cnt[i]+i ) 전체코드 #include #include using namespace std; int n; long long cnt[100002]; long long dp[100002]; void Input() { cin >> n; int value; for (int i = 0; i > value; cnt[value]++; } } int main() { Input(..

https://codeforces.com/problemset/problem/230/B Problem - 230B - Codeforces codeforces.com 조건 2초, n (1 ≤ n ≤ 10^5), xi (1 ≤ xi ≤ 10^12) 접근 이 문제는 약수가 3개인 수를 구한다. 약수가 3개인 수가 뭘까? 잘 생각해보면 소수를 ^2하면 약수가 3개인 수를 구할수 있음을 깨달을 수 있다. ex) 소수 2, 3, 5, 7의 제곱수들을 보면 4, 9, 25, 49로 모두 약수가 3개인 수들이다. 그렇다면 소수만 빨리 풀수 있다면 이 문제도 시간내에 충분히 풀수있을것이다. 풀이방법 일단 범위는 루트를 씌워 구할것이기 때문에 10^12의 루트를 씌운 10^6 + 1로 설정했다. 그외에는 그냥 에라스토테네스..

https://codeforces.com/problemset/problem/189/A Problem - 189A - Codeforces codeforces.com 풀이방법 시간은 1초, n,a,b,c는 최대 4000이다. 조건은 1. piece는 무조건 a or b or c 2. 최대로 자를수 있는 값을 구하라 완전탐색으로 할시 최악의 경우 ( a,b,c가 1, n이 4000일때 ) 4000! * 3일수 있다. 그러므로 완전탐색은 탈락이고 시간을 줄일수 있는 dp를 써보자. dp[value] : value일때 최대로 자를수 있는 개수 그리고 a, b, c를 하나씩 순서대로 밑의 조건대로 넣어보자. 1. value % piece (a or b or c) == 0 일때 dp[value] = max(dp[va..

https://codeforces.com/problemset/problem/492/B Problem - 492B - Codeforces codeforces.com 풀이방법 주어진 조건은 시간은 1초, n은 최대 1000, l은 최대 10^9 이다. n이 1000 밖에 안되므로 그냥 정렬해서 풀면 끝이다. slt sort가 어느정도의 시간이 걸리는지 정확히는 모르겠지만( 내 기억엔 O(nlogn)이었던걸로 기억함 ) 퀵소트의 최악의 경우인 O(n^2)이라도 시간은 충분하다. ㅎㅎ 전체코드 #include #include #include #include using namespace std; int N; long long L; vector a; void Input() { cin >> N >> L; long l..

https://codeforces.com/problemset/problem/158/B Problem - 158B - Codeforces codeforces.com 풀이방법 1. 4명, 3명, 2명인 그룹을 먼저 태운다 ans = numOfGroup[4] + numOfGroup[3] + numOfGroup[2]/2; 2. 1명인 그룹, 2명인 그룹을 위에 맞춰 끼워탄다. ( 1번은 3번에 2번은 2번끼리 ) numOfGroup[1] -= numOfGroup[3]; numOfGroup[2] -= (numOfGroup[2] / 2)*2; 3. 2명인 그룹, 1명인 그룹이 남았으면 그에 맞춰 계산한다. if (numOfGroup[2] > 0) { ans += 1; numOfGroup[1] -= 2; } if (..

어렵지 않은 문제도 영어 해석이 잘 안되서 못풀겠다. 엄청 쉬운 문제도 중간중간 조건을 빼먹어서 계속 틀리고.. 매일 최소 2~3문제를 풀어서 영어에 익숙해지는게 먼저인거 같다. 제목이 처음으로 풀어본 코드포스 문제인데, 뭘 풀었는지를 포스팅을 안해놔서 약간 낚시글같은 느낌이라 뭘 풀었고 처음엔 뭘 풀면 좋을지에 대한 내용을 추가해본다. ㅎㅎ 처음부터 버츄얼로 풀어보는것도 좋지만 거의 3시간 5시간 걸리기 때문에 영어해석에 문제가 있고, 영어지문에 대한 연습을 원한다면 1. PROBLEMSET에 들어가서 2. 많이 푼 문제부터 설정, difficulty를 보고 풀고싶은 문제 풀기 이렇게 차근차근 풀어가는걸 추천한다. ( 처음에는 문제수준이 어렵지 않다. ) 이 문제들은 초반엔 너무 쉬운문제밖에 없어서 알..