알고리즘/BOJ
-
[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이 왼쪽 컵홀더를 사용하지 못할 경우 아예 사용하지 못하니 이 점..
-
BOJ 17069 파이프 옮기기 2(python 3)알고리즘/BOJ 2019. 4. 11. 02:41
파이프 옮기기 2의 코드는 python 3으로 제출해도 됩니다. 파이프 옮기기 2는 1과 다르게 시간 제한이 1초에서 0.5초로 줄어들었고, N의 범위가 3~16에서 3~32로 늘어났습니다. 이 문제는 DP로 풀 수 있습니다. 이번엔 칸에 칠해진 색깔과 파이프의 색깔을 살펴봐야합니다. 노란색 파이프(→)처럼 놓일려면 아래 두 방법중에 하나를 이용해야 합니다.(배열 좌표는 x, y라고 가정) 1) x, y-1인 노란색 파이프(→) 2) x, y-1인 파란색 파이프(↘) 파란색 파이프(↘)처럼 놓일려면 아래 세 방법중에 하나를 이용해야 합니다. 1) x-1, y-1인 노란색 파이프(→) 2) x-1, y-1인 파란색 파이프(↘) 3) x-1, y-1인 초록색 파이프(↓) 초록색 파이프(↓)처럼 놓일려면 아래..
-
BOJ 17070 파이프 옮기기 1(python 3)알고리즘/BOJ 2019. 4. 11. 02:18
https://www.acmicpc.net/problem/17070 파이프 옮기기 1의 코드는 시간 제한 때문에 pypy3으로 제출해야합니다. main함수는 이렇습니다. 1 2 3 4 5 n = int(input()) D = [[*map(int, input().split())] for _ in range(n)] k = 0 dfs(0, 1, 0) print(k) Colored by Color Scripter cs k는 도착점에 도착하는 방법의 수 입니다. 파이프의 끝의 좌표가 (1,2) 이므로 (0,1)에서 dfs를 시작하도록 하였습니다. dfs함수는 이렇습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def dfs(x, y, z):# → 0, ↘ 1, ↓ 2 global k if..
-
BOJ 17135 캐슬 디펜스(Python 3)알고리즘/BOJ 2019. 4. 8. 23:22
https://www.acmicpc.net/problem/17135 일단 먼저 필요한 것이 combinations, deepcopy, deque, Max입니다. combinations는 궁수가 어디에 위치하고 있는지 모르기 때문에 모든 경우의 수를 구하기 위해 불러왔습니다. deepcopy는 원본 맵을 복사 하여 각 경우의 수마다 시뮬레이션을 돌려야 하기 때문에 맵의 수정이 필요하므로 불러왔습니다. deque는 몬스터의 좌표를 저장할 때 쓰입니다. Max는 공격할 수 있는 적이 여러 명일 때, 가장 왼쪽에 있는 적을 공격하기 위해서 만들었습니다. 이건 설정 안 해도 됩니다. 1 2 3 4 from itertools import combinations from copy import deepcopy from..
-
BOJ 13905 세부(Python 3)알고리즘/BOJ 2019. 3. 12. 14:48
https://www.acmicpc.net/problem/13905 -크루스칼 알고리즘을 사용함-재귀함수 깊이를 설정 안해주면 런타임 에러가 나옴 주의할 점은 다른 MST문제와 다르게, 매 탐색마다 출발점이랑 도착점이랑 같은 연합인지 확인해봐야 함그래야 가져갈 수 있는 최대한의 빼빼로를 출력할 수 있음 코드확인 1234567891011121314151617181920212223def F(x): if S[x]==x:return x S[x]=F(S[x]) return S[x] import syssys.setrecursionlimit(100000)input=__import__('sys').stdin.readlinen,m=map(int,input().split())s,e=map(int,input().split(..
-
BOJ 1738 골목길(Python 3)알고리즘/BOJ 2019. 3. 7. 18:03
https://www.acmicpc.net/problem/1738 이 문제는 오민식의 고민과 비슷한 문제이다. 음수 싸이클이 있을 경우 큐에 싸이클을 도는 정점을 모두 넣어주고, 큐에 있는 정점들이 코레스코 콘도까지 갈 수 있는지 없는지 확인해준다.(BFS) 만약 음수 싸이클에서 코레스코 콘도로 갈 수 있으면 -1을 출력 시작점에서 코레스코 콘도까지 갈 수 없으면 -1을 출력 갈 수 있으면 경로 리스트를 출력하면 된다. 경로 리스트는 리스트에 넣어둔 좌표를 역추적을 하여 출력하였다. 벨만포드 + BFS로 풀음 코드 확인 123456789101112131415161718192021222324252627282930313233343536from collections import dequeinput=__impo..
-
BOJ 1613 역사(Python 3)알고리즘/BOJ 2019. 2. 23. 22:02
https://www.acmicpc.net/problem/1613 플로이드 와샬 알고리즘은 단 4줄이기 때문에 외우기 굉장히 쉽다.for k for i for j , ij, ikj 이렇게만 외우면 끝 플로이드를 돌린 후서로 다른 두 사건의 번호가 주어질 때(만약 a,b라고 주어질 때) D[a][b] != INF 이면 -1D[b][a] != INF 이면 1D[a][b] == INF 이면 0을 출력하면 된다. Python으로 제출하면 시간 초과가 나기 때문에 Pypy로 제출 해야 한다. 코드 확인 123456789101112131415n,m=map(int,input().split())Max=float('inf')S=[[Max]*(n+1) for _ in range(n+1)]for i in range(m): ..