본문 바로가기
728x90

bruteforce

[백준알고리즘] 15686번: 치킨 배달 -Python [백준알고리즘] 15686번: 치킨 배달 -Python https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 브루트 포스 방식으로 문제를 풀 수 있었다. 모든 집에서 최대 m개의 치킨집을.. 더보기
[백준알고리즘] 14889번: 스타트와 링크 -Python [백준알고리즘] 14889번: 스타트와 링크 -Python https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 브루트 포스방식으로 문제를 풀었다. N//2명의 인원씩 A, B팀으로 나누어주었다. 이때 모든 팀원 배치를 하기 위해서 itertools의 combinations를 사용했다. 구한 팀 배치마다 각 팀원들의 모든 팀 능력치를 합해주기 위해서 이중 for문을 돌렸다. from sys import maxsize from itertools import combinat.. 더보기
[백준알고리즘] 14502번: 연구소 -Python [백준알고리즘] 14502번: 연구소 -Python https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 20200423 아래에 PyPy3로만 통과한 코드를 추가했다. PyPy로만 통과가 됐지.. 더보기
[백준알고리즘] 14501번: 퇴사 -Python [백준알고리즘] 14501번: 퇴사 -Python https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사하기 전까지 가장 많은 돈을 벌 수 있도록 해야 한다. 며칠에 걸리는 상담인지에 따라 며칠간 상담을 추가로 할 수 없을 수도 있다. 나는 dp처럼 문제를 풀었다. 1일 차부터 순서대로 선택을 하면서 각 날짜의 일을 했을 때 최대로 벌 수 있는 금액을 유지한다. 그리고 이 최대로 벌 수 있는 금액에 다음에 할 수 있는 일 들의 금액을 더하면서 유지한다. 음... 코드를 보는 게 설명보다 쉬워 보인다... 배열로 비교를 해보도록 하자. 처음의 값은 다음과 같다. data = [(3, .. 더보기
728x90

티스토리툴바