분류 전체보기
[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..
[BaekJoon] 백준 14500번 테트로미노
[BaekJoon] 백준 14500번 테트로미노 🎈문제 https://www.acmicpc.net/problem/14500 💬설명 어려운 문제는 아니었는데 어떻게든 bfs로 풀어보려고 하다가 오래 걸렸다. 결국 bfs로 못품.. bfs로 푸는 경우 ㅁ 모양의 테트로미노를 처리할 수 없어서 visit 여부를 체크하지 말아야 하는데 그 경우 시간 초과가 난다. 그럼 visit 배열을 다시 추가해야 하고 그럼 ㅁ 모양을 처리할 수 없고,, 무한 반복,,ㅠㅠ 결국 dfs -> 백트래킹으로 풀었더니 5분만에 풀었다. 포인트 dfs -> 백트래킹으로 하나씩 들어가면서 풀어줌 4개가 완성되면 max_value 업데이트 ㅓ, ㅏ, ㅗ, ㅜ 모양의 경우 dfs로 처리할 수 없어 예외로 따로 코드를 짜줌 👩💻코드 # B..
[BaekJoon] 백준 14499번 주사위 굴리기
[BaekJoon] 백준 14499번 주사위 굴리기 🎈문제 https://www.acmicpc.net/problem/14499 💬설명 전형적인 삼성의 구현문제 주사위를 굴리는 걸 구현해야 해서 초반에 고민이 필요했다. 푸는건 금방 풀었다. dice 배열과 dice_num 딕셔너리로 주사위의 위치와 방향을 표현해줬다. 👩💻코드 # BaekJoon14499.py N, M, x, y, k = map(int, input().split()) board = [[] for _ in range(N)] for i in range(N): board[i] = list(map(int, input().split())) operations = list(map(int, input().split())) dice = [i for i..
[BaekJoon] 백준 17779번 게리맨더링 2
[BaekJoon] 백준 17779번 게리맨더링 2 🎈문제 https://www.acmicpc.net/problem/17779 💬설명 삼성 기출이라 시간재고 풀었더니 1시간 30분정도 걸렸다. 구현문제라 어렵진 않았는데 5번 구역을 구하는 부분에서 꽤 애먹었다. 더 깔끔하게 구할 수 있을 것 같은데.. 문제에서 주어지는 구역들의 범위 ..
[Programmers] 카펫
[Programmers] 카펫 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42842 💬설명 근의 공식으로 풀 수 있었던 문제 변을 각각 x, y라고 하면 x + y = (brown + 4) / 2, xy = yellow + brown 이 된다. yellow와 brown을 알고 있으니 x, y를 변수로 둬서 근의 공식으로 풀면된다. 👩💻코드 def solution(brown, yellow): a = (brown + 4) / 2 b = yellow + brown x = (a + (a ** 2 - 4 * b) ** (1/2)) / 2 y = (a - (a ** 2 - 4 * b) ** (1/2)) / 2 return sorted([x, y], rever..