알고리즘
-
[BOJ 5585, C++] 거스름돈알고리즘/BOJ 2021. 7. 26. 17:09
https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 풀이 언제나 거스름돈의 개수가 가장 적게 줘야하므로 가장 큰 단위부터 내림차순으로 거스름돈을 주면 된다. 거스름돈의 개수는 몫으로 거스름돈을 뺀 나머지는 나머지로 구할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include using namespace std; using ll = l..
-
[BOJ 2810, C++] 컵홀더알고리즘/BOJ 2021. 7. 26. 17:06
그리디 레벨이 엄청 낮길래 DP처럼 브론즈부터 플레5까지 풀기로 결정하였다. https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 풀이 컵홀더를 되도록이면 왼쪽에 있는 컵홀더를 사용하는 것이 최적해이다. 컵홀더는 왼쪽 아니면 오른쪽만 사용할 수 있으니 for문을 사용하여 순서대로 좌석을 확인하면 i번째 좌석 차례엔 무조건 오른쪽 컵홀더는 비어있다는 것이 보장이 된다. 그래서 왼쪽 컵홀더가 비어있는지 확인하여 왼쪽 컵홀더 우선순위로 컵홀더를 사용하면 된다. 이때 커플석인 경우에 왼쪽 L이 왼쪽 컵홀더를 사용하지 못할 경우 아예 사용하지 못하니 이 점..
-
Codeforces Round #701 (Div. 2) A ~ B알고리즘/Codeforces 2021. 2. 13. 03:00
codeforces.com/contest/1485 Dashboard - Codeforces Round #701 (Div. 2) - Codeforces codeforces.com 풀은 문제: 없음 ( + A, B ) 못 풀은 문제: A, B, C, D, E 풀이만 보고 풀은 문제: 코드와 풀이를 보고 풀은 문제: 점수 수직하강할 예정 A번에서 막혔을 때 제출을 안하고 아예 참가하지 말았어야 했다 A. Add and Divide a = 10**9이므로 대충 b = 10**5이상부터는 답이 1 아니면 2가 나오게 된다. 답이 1이 나오는 조건은 b > a일 때이고, 답이 2가 나오는 조건은 b**2 > a인데, 이 내용이 윗 줄을 포함하고 있으므로 그다음부터는 for문을 이용하여 구현해주면 된다. 주의할 점은..
-
Codeforces Round #546 (Div. 2) A ~ C알고리즘/Codeforces 2021. 2. 9. 22:12
codeforces.com/contest/1136 Dashboard - Codeforces Round #546 (Div. 2) - Codeforces codeforces.com 풀은 문제:A, B, C 못 풀은 문제: D, E 풀이만 보고 풀은 문제: 코드와 풀이를 보고 풀은 문제: 난이도 A - 800 B - 1000 C - 1500 D - 1800 E - 2200 C번 아이디어를 뒤늦게 생각해내서 아쉽 A. Nastya Is Reading a Book 챕터가 몇장부터 몇장까지 있는지 입력값에서 보여주고, 읽어야할 남은 챕터가 몇인지 구해야한다. 주의할 점은 입력값이 k이면 k-1쪽까지 읽었다는 것이다. def main(): n = int(input()) D = [[*map(int,input().spl..
-
Codeforces Round #545 (Div. 2) A ~ D알고리즘/Codeforces 2021. 2. 8. 22:16
codeforces.com/contest/1138 Dashboard - Codeforces Round #545 (Div. 2) - Codeforces codeforces.com 풀은 문제: A, B, C 못 풀은 문제: D, E, F 풀이만 보고 풀은 문제: 코드와 풀이를 보고 풀은 문제: 난이도 A - 900 B - 1800 C - 1600 D - 1600 E - 2500 F - 2400 어제 코포 라운드가 있었는데 오늘 수강신청하는 날이라 괜히 늦잠잘까봐 안했다. 등수가 꽤 높다했더니 난이도보니까 B에서 다들 막혔나보다. 모든 문제를 한 번에 통과할 경우 퍼포먼스가 퍼플이 나올 수 있을 것 같아서 좀 아쉽다 A - Sushi for Two [2,2,2,1,1,1] [1,1,2,2] 처럼 1이 연속적으..
-
Codeforces Round #699 (Div. 2) A ~ C알고리즘/Codeforces 2021. 2. 6. 03:27
codeforces.com/contest/1481 Dashboard - Codeforces Round #699 (Div. 2) - Codeforces codeforces.com 풀은 문제: A, B 못 풀은 문제: C, D, E 풀이를 보고 풀은 문제: 코드와 풀이를 보고 풀은 문제: C 난이도 A - B - C - D - E - C번 에디토리얼을 봤는데 아이디어는 맞았지만 코드 한 줄을 추가 안해서 틀렸다... A - Space Navigation 문자열 s를 일부 지워서 목적지까지 도착할 수 있는지 물어보는 문제이다. 그래서 U, D, R, L 의 개수를 각각 전부 세준다음 목적지까지 이동할 수 있는지 찾으면 된다. 주의할 점은 px와 py가 음수일 때 -를 붙여서 U,D,R,L 갯수보다 작으면 된다..
-
Codeforces Round #544 (Div. 3) A~D,F1알고리즘/Codeforces 2021. 2. 4. 23:05
codeforces.com/contest/1133 Dashboard - Codeforces Round #544 (Div. 3) - Codeforces codeforces.com 풀은 문제: A, B, C, F1 못 풀은 문제: D, E, F2 풀이만 보고 풀은 문제: D 코드와 풀이를 보고 풀은 문제: 난이도 A - 1000 B - 1200 C - 1200 D - 1500 E - 1800 F1 - 1600 F2 - 1900 D번은 쉬운 문제였는데 문제를 읽었으면서 같은 index끼리 비교한다는 내용을 까먹고 정수론으로 뭐 어떻게 하는줄 알아서 걸렀는데 다시 읽어볼걸 그랬다 ㅠㅠ 이것만 풀었어도 퍼포먼스가 1800점대가 나오는거라 아쉽다 E번은 dp인데 해설을 봐도 어떻게 푸는지 모르겠다. A. Middl..
-
Codeforces Round #542 (Div.2) A ~ D2알고리즘/Codeforces 2021. 2. 3. 18:36
codeforces.com/contest/1130 Dashboard - Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) - Codeforces codeforces.com 풀은 문제: A, B, C, D1 못 풀은 문제: D2, E 풀이를 보고 풀은 문제: D2 코드와 풀이를 보고 풀은 문제: 난이도 A - 800 B - 1200 C - 1400 D1 - 1700 D2 - 1800 E - 2000 A번에서 2번이나 틀리고 맞췄다. A번은 빨리 풀고 넘겨야한다는 압박감 때문에 검토 안하고 바로바로 제출하는데 좀 아쉬웠다. D1, D2같이 쉬운 버전/어려운 버전으로 나뉘는 문제에서 쉬운 버전은 보통 브루트 포스로 푸는 문제가 많길래 시간을 계산해보니까..