CS/Algorithm 문제
[BaekJoon] 백준 20057번 마법사 상어와 토네이도
[BaekJoon] 백준 20057번 마법사 상어와 토네이도 🎈문제 https://www.acmicpc.net/problem/20057 💬설명 1시간 10분 정도 걸렸다. 마지막에 % 계산을 잘못 해줘서 틀렸다가 다시 품 포인트는 1. 회오리 모양으로 돌기 2. 모래가 흩어질때 방향에 따라 어느 위치에 몇 퍼센트 퍼질지 였던 것 같다. 모두 방향만 잘 설정해주면 쉽게 풀 수 있다. 근데 그 방향을 설정하는게 꽤 까다로웠다,, 수학문제 느낌,, 👩💻코드 # BaekJoon20057.py N = int(input()) arr = [[] for _ in range(N)] for i in range(N): arr[i] = list(map(int, input().split())) dx = [0, 1, 0, -1..
[BaekJoon] 백준 21611번 마법사 상어와 블리자드
[BaekJoon] 백준 21611번 마법사 상어와 블리자드 🎈문제 https://www.acmicpc.net/problem/21611 💬설명 복잡한 구현 문제. 푸는데 2시간 정도 걸렸다. 구현은 1시간 안에 했는데 자꾸 틀렸다고 나와서 히든 테케에서 틀린 부분 찾는데 1시간 걸렸다. 어쨋든 스스로 풀었으니까 일단 만족,, 놓친 부분은 다음과 같다. 각각 step을 수행할 때 arr가 빈값인 경우 예외 처리 연속하는 구슬의 개수를 세거나 구슬을 그룹별로 묶을 때 마지막에 세줘야 하는 것을 빼먹음 👩💻코드 N, M = map(int, input().split()) board = [[] for _ in range(N)] for i in range(N): board[i] = list(map(int, inp..
[BaekJoon] 백준 21610번 마법사 상어와 비바라기
[BaekJoon] 백준 21610번 마법사 상어와 비바라기 🎈문제 https://www.acmicpc.net/problem/21610 💬설명 문제를 푸는데는 1시간 10분정도 걸렸고, 구현문제였다. 그대로 따라서 구현하면 되는데 마지막에 이전에 구름이 있는 위치면 새로운 구름이 생기면 안되는 조건에서 시간초과가 나서 헤맸다. if [i, j] in clouds로 하면 clouds 배열을 전부 다시 돌기 때문에 시간이 오래 걸린다. 따라서 visit 배열을 따로 만들어줘서 시간을 단축시켰다. 👩💻코드 # BaekJoon21610.py N, M = map(int, input().split()) arr = [[] for _ in range(N)] for i in range(N): arr[i] = list(..
[BaekJoon] 백준 14889번 스타트와 링크
[BaekJoon] 백준 14889번 스타트와 링크 🎈문제 https://www.acmicpc.net/problem/14889 💬설명 combination을 직접 구현해서 모든 조합을 구하고 각각에 대해 점수차를 구해줘서 최소값을 구해줬다. itertools 썼으면 금방 풀었을텐데 직접 구현하려다 보니 조금 오래걸린듯 하다,, 👩💻코드 # BaekJoon14889.py N = int(input()) arr = [[] for _ in range(N)] for i in range(N): arr[i] = list(map(int, input().split())) combi = [] result = float('inf') def calculate(team): global arr, N, result another..
[BaekJoon] 백준 14888번 연산자 끼워넣기
[BaekJoon] 백준 14888번 연산자 끼워넣기 🎈문제 https://www.acmicpc.net/problem/14888 💬설명 연산자로 만들 수 있는 모든 조합 구해서 계산해주면 된다. 조합을 Itertools 를 사용하지 않고 직접 구현해보았다. 어렵지 않은 문제 👩💻코드 # BaekJoon14888.py N = int(input()) arr = list(map(int, input().split())) # 숫자들 ops = list(map(int, input().split())) # + - * % 의 개수 max_result = float('-inf') min_result = float('inf') def dfs(lis): global ops, arr, max_result, min_resul..
[BaekJoon] 백준 14503번 로봇 청소기
[BaekJoon] 백준 14503번 로봇 청소기 🎈문제 https://www.acmicpc.net/problem/14503 💬설명 문제에 나오는 대로만 구현하면 되는 어렵지 않은 문제 👩💻코드 # BaekJoon14503.py answer = 0 N, M = map(int, input().split()) pos = [0, 0] pos[0], pos[1], direction = map(int, input().split()) arr = [[] for _ in range(N)] for i in range(N): arr[i] = list(map(int, input().split())) visited = [[False for _ in range(M)] for _ in range(N)] dx = [-1, 0, ..
[BaekJoon] 백준 14502번 연구소
[BaekJoon] 백준 14502번 연구소 🎈문제 https://www.acmicpc.net/problem/14502 💬설명 데이터의 크기가 크기 않았기 때문에 brute force + bfs로 풀 수 있었던 문제 문제 이해하고 푸는데 30분정도 걸렸다. 과정 벽을 세울 3개의 빈공간을 조합으로 고른다 선택한 3군데에 벽을 세운다 bfs로 바이러스와 연결된 모든 곳의 개수를 센다 (전제 블럭의 개수 - 바이러스랑 연결된 곳의 개수 - 벽의 개수)를 해주면 안전지역의 개수를 구할 수 있다. 구한 안전구역의 개수를 최대값으로 update 해준다. 👩💻코드 # BaekJoon14502.py from itertools import combinations from collections import deque ..
[BaekJoon] 백준 14501번 퇴사
[BaekJoon] 백준 -번 문제이름 🎈문제 https://www.acmicpc.net/problem/14501 💬설명 전형적인 dp 문제 점화식은 다음과 같다. dp(n) = (n번째날 ~ 마지막 날) 최대 수익 이라고 할 때 dp(n) = max( dp(n+1), P[n] + dp(n + T[n]] ) 말로 풀어서 말하자면 (n번째 날부터 마지막 날까지의 최대 수익)은 (n+1번째 날 ~ 마지막 날까지의 최대 수익)과 (n번째 날의 수익 + (n + Tn)번째 날부터 마지막 날까지의 최대 수익) 중 더 큰 값이다. 주어진 예시를 뒤에서부터 따져보면 이해가 간다. 👩💻코드 # BaekJoon14501.py N = int(input()) T = [0 for _ in range(N)] P = [0 fo..