본문 바로가기

알고리즘/백준

 (16)
[Python] 백준 16236 : 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 방법 물고기를 먹으러갈 때마다 bfs로 이동한다. bfs로 이동하고 이동한 칸 수 만큼 answer에 더해준다. 현재 상어의 크기 만큼 물고기를 먹었으면 상어의 크기 + 1해준다. 틀렸던 부분 ) "먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기 -> 가장 위에 -> 가장 왼쪽에" : 이 부분 구현은 bfs와 move의 순서 조정으로 할 수 있을 줄 알았는데, 먹을 수 있는 물..
[Python] 백준 16235 : 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제에 나온 그대로 봄,여름,가을,겨울을 구분하여 구현하면 된다. 전체 코드 move = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)] def spring(): temp = [[0]*N for _ in range(N)] for i in range(N): for j in range(N): if not tree[i][j]: continue new = [] for x in range(len(tree[..
[Python] 백준 16234 : 인구 이동 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 과정 각 지점에서 출발해서, 인접하고 현재 지점과의 차이가 l이상 r이하인 곳들을 bfs/dfs를 통해서 다 방문한다. 방문이 가능하다는 것은 하나의 연합이 된다는 것을 의미한다. visted는 전체 출발에 대해서 하나만 정의해서 쓰면 된다. 전체 코드 move = [(0,1), (1,0), (-1,0), (0,-1)] def dfs(i, j): now = [] total = 0 cnt = ..
[Python] 백준 15684 : 사다리 조작 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 방법 i에서 출발했을 때, 어디서 끝나는지 return해줄 함수가 필요하다. board[a][b] = 1은 a번 점선 위치로 b에서 b+1로 갈 수 있음을 의미하고, board[a][b] = -1은 a번 점선 위치로 b에서 b-1로 갈 수 있음을 의미한다. board[a][b] = 0이라면 a번 점선 위치로 b세로줄에서 갈 수 있는 곳이 없음을 의미한다. 브루투포스를 이용해서 아직 연결되지 않은 가로줄 중 3개 이하를 뽑았을 때, i에서 시작하면 i로 끝나..
[Python] 백준 17609 : 회문 풀이 방법 투포인터로 하나씩 비교한다. 만약 좌우가 다른 문자가 나올 경우, left+1해서 검사하고 right-1해서 검사한다. 두 검사 결과 중 하나라도 회문이라면 유사회문이다. 전체 코드 def check(left, right): while left < right: if s[left] == s[right]: left += 1 right -= 1 else: return False return True def twopointer(left, right): while left < right: if s[left] == s[right]: left += 1 right -= 1 else: if check(left+1, right) or check(left, right-1): return 1 return 2 ret..
[Python] 백준 2531 : 회전 초밥 www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 방법 문제 이해 : 초밥을 k개 연속으로 먹었을 때 먹을 수 있는 최대 종류를 구하는 것이다. left부터 right까지 먹을 때, 먹을 수 있는 초밥의 종류를 canEat이라는 딕셔너리에 저장한다. 먹을 수 있는 초밥의 종류의 개수는 cnt에 저장한다. '회전' 초밥이기 때문에 0~k까지 뿐만아니라 n-1~k-1까지 순환할 수 있음을 잊으면 안된다. -> right..
[Python] 백준 1700 멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 방법 반복문으로 전기용품을 하나씩 방문하면서 플러그를 빼야하는지 안 빼도 되는지 체크한다. 플러그가 N개 이하로 꽂혀있거나, 현재 확인하려는 전기용품이 이미 꽂혀있다면 뽑지 않아도 된다. 뽑아야할 때, 꽂혀있는 플러그 중에서 이후 가장 나중에 사용되는 전기용품 또는 이후 사용되지 않는 전기용품을 먼저 뽑는다. N과 K모두 100이하 이므로 시간초과에 대해서 생각하지 않아도 된다. 전체 코드 n, k = map(int, input().split()) arr ..
[Python] 백준 3955 캔디 분배 (확장 유클리드 알고리즘) 백준 3955 캔디 분배 🍏 유클리드 호제법 설계 C : 한 봉지의 사탕 개수, K : 사람 수 x = 1 인당 먹을 사탕 개수 y = 구매해야할 사탕 개수 Kx + 1 = Cy 를 만족하는 y를 찾는 것이다. 확장 유클리드 호제법에 맞게 식을 수정하면, Cy - Kx = 1 을 만족하는 y를 찾는 것이다. 유클리드 호제법에서 a = C, b = -K, 1 = g이다. 🍍 예외 처리 g = 1 이어야 하기 때문에 gcd(C, K) == 1 이어야 한다. K와 C의 gcd가 1이 아니라면 IMPOSSIBLE 구한 y가 10^9보다 크면 IMPOSSIBLE C == 1 일 때, 사탕 한 봉지에 사탕 한 개만 들었으니까 사람수 + 1만큼 사탕을 사면 된다. 따라서 답은 K+1 이고, K+1 > 10^9라면 I..
반응형

티스토리툴바