Doby's Lab

https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에 www.acmicpc.net Solved By: Implementation Try 1) 실제로 모든 값을 계속 구하다가 O(NQ)로 인해 시간 초과가 났습니다. Try 2) 식을 정리해보다가 다음과 같은 규칙을 발견했습니다. 계산 식을 통해 구한 값이 다음 쿼리에 대한 값과 연관이 있습니다. 예를 들어 N의 크기가 5이고, Query에서 3을 요청한다면 3번째 원소..

https://www.acmicpc.net/problem/13268 13268번: 셔틀런 지훈이가 쓰러진 구간을 하나의 숫자로 출력한다. 시작점을 구간 0, 시작점부터 (시작점 미포함) 첫 번째 콘까지 (첫 번째 콘 포함) 구간을 1, 첫 번째 콘 (미포함) 부터 두 번째 콘까지 (포함) 구간 www.acmicpc.net Solved By: Implementation 이번 문제는 여러모로 뿌듯하네요. 구현 문제이다 보니 생각할 부분들이 많아서 풀어낸 뒤 성취감 Python으로 어려운 문제 풀어보기 성공 암튼 솔루션으로 넘어가 보겠습니다. 우선 자연수의 의미가 애매모호해서 0은 Exception으로 처리했습니다. 5m마다 콘이 있고, 20m까지 있어서 이동을 5m씩 해주는 게 좋지 않을까라는 생각을 했습니..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net Solved By: Knapsack DP 시간을 무게라고 두고, 배점을 가치라고 두었을 때, Knapsack DP를 돌려서 최대 이득 배점을 구해내면 됩니다. #include using namespace std; int cache[101][10001]; pair test[101]; int n, t; int main(){ cin >> n >> t; for..

https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net Solved By: Knapsack DP #include using namespace std; pair chapter[21]; int cache[21][201]; // 일 수 == 무게, 페이지 수 == 가치 int n, m; int main(){ cin >> n >> m; for(int i = 1; i > chapter[i].first >> chapter[i].s..

https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net Solved By: Knapsack DP 여전히 Knapsack DP 공부 중.. #include using namespace std; int cache[21][101]; pair human[21]; // first == 체력, second == 기쁨 int n; int main(){ cin >> n; for(int i = 1; i > human[i].first; } for(int i = 1; ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Solved By: Knapsack DP 처음으로 시도해본 Knapsack DP문제입니다. 이론을 공부하면서 코드를 써봤는데 아직 완전히 이해되지는 않았습니다. 각 아이템 당 무게와 가치는 pair형 배열을 선언하여 저장해주었습니다. #include using namespace std; int n, k; int cache[101][..

https://www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net Solved By: Deque 뺀 사람의 수가 M명이 되었을 경우, 방향을 바꿔야 하기 때문에 큐가 아닌 덱을 사용하여 양방향을 고려하게 해주고, M명이 되었을 때 bool type flag변수를 사용하여 방향을 바꿀지 말지에 대한 여부를 설정해줬습니다. #include #include using namespace std; int main(){ ios_base::sync_with_stdii(false); cin.tie(NULL); int n, k..

파이썬 기본 문법 챙길 겸 올솔 배경이 예쁘길래 한 번 시간 내어서 해봤습니다😁😁