728x90 반응형 Python/백준26 백준 치킨 배달 [15686] 파이썬(Python) 코드 + 해설 문제 설명도시가 N×N 크기의 2차원 격자로 주어집니다. 각 칸에는 빈 칸(0), 집(1), 치킨집(2) 중 하나가 있다.도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다. 여기서 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.프랜차이즈 본사에서는 수익을 극대화하기 위해 일부 치킨집을 폐업시키려고 한다. 최대 M개의 치킨집을 남기고 나머지는 폐업시킬 수 있다. 이때, 도시의 치킨 거리를 최소화하는 방법을 찾는 것이 문제의 목표이다.입력 및 제한 조건첫째 줄: N(2 ≤ N ≤ 50), M(1 ≤ M ≤ 13)둘째 줄부터 N개의 줄에 도시 정보가 주어진다.0: 빈 칸1: 집 (집의 개수는 최소 1개 이상, 최대 2N개 이하)2: 치킨집 (치킨집의 개수는 M 이상, 13 이하)목표폐업시키지 않을 M.. 2024. 10. 31. 백준 드래곤 커브 [15685] 파이썬(Python) 코드 + 해설 문제 설명드래곤 커브는 시작 점, 시작 방향, 세대를 가진다. 0세대 드래곤 커브는 길이가 1인 선분이며, 이후 세대는 이전 세대의 드래곤 커브를 끝점을 기준으로 시계 방향으로 90도 회전한 후, 끝점에 붙여서 만든다.주어진 여러 개의 드래곤 커브를 그린 후, 좌표 평면 위에서 네 꼭짓점이 모두 드래곤 커브의 일부인 1×1 크기의 정사각형의 개수를 구하는 문제이다.입력첫째 줄: 드래곤 커브의 개수 N (1≤N≤20)다음 N개의 줄: 각 드래곤 커브의 정보 x,y,d,gx,y: 드래곤 커브의 시작 점 (0≤x,y≤100)d: 시작 방향 (0≤d≤3)0: 오른쪽 (→)1: 위쪽 (↑)2: 왼쪽 (←)3: 아래쪽 (↓)g: 세대 (0≤g≤10)출력네 꼭짓점이 모두 드래곤 커브의 일부인 1×1 크기의 정사각형의.. 2024. 10. 31. 백준 사다리 조작 [15684] 파이썬(Python) 코드 + 해설 이 문제는 메모리 초과와 시간 초과가 굉장히 많이 나는 문제입니다. 문제 소개사다리 조작은 세로선과 가로선으로 이루어진 사다리 게임을 조작하여, 각 세로선의 결과가 자기 자신이 되도록 만드는 문제입니다. 세로선의 개수 N, 가로선을 놓을 수 있는 위치의 개수 H, 이미 놓인 가로선의 개수 M이 주어집니다. 최대 3개의 가로선을 추가하여 원하는 결과를 얻을 수 있는 최소의 가로선 개수를 구하는 것이 목표입니다.입력 조건:세로선의 개수 N: 2≤N≤102 가로선을 놓을 수 있는 위치의 개수 H: 1≤H≤30이미 놓인 가로선의 정보 M개출력 조건:추가해야 하는 가로선의 최소 개수 (단, 3개를 초과하면 -1을 출력) 문제 분석이 문제는 가능한 모든 가로선의 조합을 탐색하여 원하는 결과를 찾는 완전 탐색(Bru.. 2024. 10. 30. 백준 감시 [15683] 파이썬(Python) 코드 + 해설 문제 설명사무실은 N×M 크기의 격자로 표현됩니다.N,M ≤ 8이므로 격자의 크기는 최대 8 × 8 입니다.격자의 각 칸에는 다음 중 하나가 있습니다:빈 칸 (0): 아무것도 없는 공간입니다.벽 (6): CCTV의 시야를 가로막는 벽입니다.CCTV (1~5): CCTV 카메라가 설치되어 있습니다.CCTV는 총 5가지 종류가 있으며, 각 종류마다 감시할 수 있는 방향이 다릅니다.목표: CCTV의 방향을 적절히 설정하여 사각지대(감시되지 않는 영역)의 최소 크기를 구하는 것입니다.CCTV 종류 및 감시 방향CCTV의 종류에 따라 감시할 수 있는 방향이 정해져 있습니다:1번 CCTV: 한 방향 감시 (총 4가지 경우)2번 CCTV: 두 방향 감시 (서로 반대 방향, 총 2가지 경우)3번 CCTV: 두 방향 감.. 2024. 10. 29. 백준 톱니바퀴 [14891] 파이썬(Python) 코드 + 해설 문제 설명4개의 톱니바퀴가 일렬로 놓여 있습니다.각 톱니바퀴는 8개의 톱니를 가지고 있으며, 톱니는 N극(0) 또는 S극(1)을 가집니다.톱니바퀴는 시계 방향(1) 또는 반시계 방향(-1)으로 회전할 수 있습니다.톱니바퀴가 회전할 때, 인접한 톱니바퀴와 맞닿은 톱니의 극에 따라 인접한 톱니바퀴가 회전할 수 있습니다.맞닿은 톱니의 극이 다르면, 인접한 톱니바퀴는 반대 방향으로 회전합니다.맞닿은 톱니의 극이 같으면, 인접한 톱니바퀴는 회전하지 않습니다.K번의 회전이 주어지며, 각 회전에 대한 톱니바퀴 번호와 회전 방향이 주어집니다.모든 회전이 끝난 후, 각 톱니바퀴의 12시 방향 톱니의 극에 따라 점수를 계산합니다:1번 톱니바퀴: S극이면 1점2번 톱니바퀴: S극이면 2점3번 톱니바퀴: S극이면 4점4번 톱.. 2024. 10. 29. 백준 경사로 [14890] 파이썬(Python) 코드 + 해설 문제 이해하기문제 설명지도 크기: N×N ( 2≤N≤100 2≤N≤100 )각 칸에는 그곳의 높이가 적혀 있습니다 ( 1≤높이≤10 1≤높이≤10 ).길: 한 행 또는 한 열 전체를 말하며, 총 2N개의 길이 있습니다.길을 지나갈 수 있으려면 다음 조건을 만족해야 합니다:길에 속한 모든 칸의 높이가 같거나,경사로를 놓아서 지나갈 수 있어야 합니다.경사로 놓는 조건경사로의 특성:높이: 1길이: L ( 1 ≤ 𝐿 ≤ 𝑁 1≤L≤N )경사로의 개수는 충분히 많습니다.경사로를 놓을 수 있는 조건:경사로는 낮은 칸에 놓이며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 합니다.낮은 칸과 높은 칸의 높이 차이는 1이어야 합니다.경사로를 놓을 낮은 칸의 높이는 모두 같아야 합니다.이미 경사로를 놓은 곳에는 다.. 2024. 10. 28. 백준 스타트와 링크 [14889] 파이썬(Python) 코드 + 해설 문제 이해하기이 문제는 브루트 포스와 백트래킹 관련 문제입니다.해결 방법팀 조합 생성: N명의 사람들 중 N/2명을 선택하여 한 팀을 구성하고, 나머지 N/2명은 다른 팀을 구성합니다.능력치 계산: 각 팀에 대해 팀에 속한 모든 쌍의 사람들에 대해 능력치를 합산합니다.차이 계산 및 최소화: 두 팀의 능력치 합의 차이를 계산하고, 그 중 최소값을 찾습니다.구현 방법입력 받기N과 능력치 행렬 SSS를 입력받습니다.사람의 번호는 0부터 N-1까지로 설정합니다.모든 팀 조합 생성N명의 사람들 중 N/2명을 선택하는 모든 조합을 생성합니다.itertools.combinations를 사용합니다.조합의 대칭성을 이용하여 전체 조합의 절반만 고려합니다.팀 능력치 합 계산각 팀 조합에 대해 다음을 수행합니다:팀 A의 능.. 2024. 10. 27. 백준 연산자 끼워넣기 [14888] 파이썬(Python) 코드 + 해설 해결 전략이 문제는 가능한 모든 연산자 배치를 시도하여 결과의 최댓값과 최솟값을 찾는 백트래킹(DFS) 문제입니다.알고리즘 개요입력받기: 수열과 연산자 개수를 입력받습니다.백트래킹 함수 구현:현재까지의 계산 결과, 사용한 연산자 개수, 수열의 인덱스를 인자로 받습니다.모든 연산자 배치를 시도합니다.각 연산자 배치마다 결과를 계산하고, 최댓값과 최솟값을 갱신합니다.나눗셈 구현:나눗셈에서 음수 처리를 문제의 요구사항에 맞게 구현합니다.결과 출력: 최종적으로 구한 최댓값과 최솟값을 출력합니다. 핵심 포인트백트래킹을 통한 완전 탐색: 모든 가능한 연산자 배치를 시도하여 최적해를 찾습니다.나눗셈의 정확한 구현: 파이썬의 나눗셈 연산과 문제의 요구사항의 차이를 이해하고 올바르게 구현합니다.연산자 우선순위 무시: 계.. 2024. 10. 26. 백준 로봇 청소기 [14503] 파이썬(Python) 코드 + 해설 문제 이해하기이 문제는 로봇 청소기가 방을 돌아다니며 청소하는 영역의 개수를 구하는 것이다.문제 설명방의 구조: N x M 크기의 직사각형 방이 있고, 각 칸은 벽(1) 또는 빈 칸(0)이다.로봇 청소기의 위치와 방향:좌표 (r, c)에 위치해 있으며, 방향 d를 가지고 있다.방향 d는 북(0), 동(1), 남(2), 서(3) 중 하나이다.로봇 청소기의 작동 방식:현재 위치를 청소한다.현재 위치에서 다음을 반복한다:주변 4칸 중 청소되지 않은 빈 칸이 있는지 확인한다.있다면, 반시계 방향으로 90도 회전하고, 전진한다.없다면, 바라보는 방향을 유지한 채로 후진한다.후진할 수 없다면 작동을 멈춘다.청소한 칸의 개수를 구한다.해결 방법: 시뮬레이션 구현이 문제는 로봇 청소기의 동작을 그대로 구현하는 시뮬레이.. 2024. 10. 25. 이전 1 2 3 다음 728x90 반응형
