🥇 Problem Solving

[Python] BOJ / 2133번 / 타일 채우기

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 📝 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 📜 풀이 기본적으로 n이 홀수인 경우는 타일을 모두 채울 수 없음 n = 2부터 시작하여 벽의 크기가 2씩 증가할 때마다 새로운 모양으로 벽을 채우는 경우가 2씩 늘어남 따라서 다음과 같은 규칙이 성립됨 n = 2일 때의 경우의 수는 3가지 n = 4일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 2일 때의 경우의 수) + 2 n = 6일 때의 경우의 수는 (n = 2일 때의 경우의 수) x (n = 4일 때의 경우의 수) + 2 n = 8일 때의 경우의 수는 (n ..

[Python] BOJ / 2617번 / 구슬 찾기

2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 📝 풀이 N개의 구슬에 대한 M개의 쌍의 대한 비교 결과를 통해 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램 DFS, BFS 등 여러가지 방법으로 구현할 수 있지만 필자의 경우 플로이드-와샬 알고리즘을 사용하였다. 알고리즘의 진행 과정은 다음과 같음 구슬 쌍에 대한 비교 결과를 배열에 저장 위 과정에서 나온 배열을 통해 플로이드-와샬 알고리즘 수행 이후 완성된 배열에서 각 구슬에 대해 더 가벼운 구슬과 더 무거운 구슬의 개수..

[Python] BOJ / 2665번 / 미로만들기

2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 📝 풀이 n x n 바둑판 모양으로 총 n^2개의 방이 있을 때, 윗줄 맨 왼쪽 시작방에서부터 아랫줄 맨 오른쪽 끝방으로 이동하는데 필요한 방의 색을 바꾸는 횟수를 최소로 하는 경우를 구하는 프로그램 흰방은 1, 검은방은 0으로 나타내며 검은방은 지나갈 수 없는 방이다. 다익스트라 알고리즘으로 구현할 수 있으며 최소 힙을 방의 색을 바꾼 횟수를 기준으로 정렬한다. 💻 소스코드 import sys import heapq input = sys.stdin.readli..

[Python] BOJ / 6497번 / 전력난

6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 📝 풀이 m개의 집(노드)과 n개의 길(간선)으로 구성된 도시(연결 그래프)가 주어지고 해당 도시에서 가로등 일부를 소등하였을 때(일부 간선을 제거하였을 때) 절약할 수 있는 최대 액수를 구하는 프로그램 일부 간선을 제거한 연결 그래프에서 모든 두 노드 쌍은 서로 연결되어 왕래할 수 있어야 한다. 전형적인 MST 알고리즘으로 구현할 수 있다. 크루스칼 알고리즘, 최소 힙 자료구조 사용 💻 소스코드 import sys input = sys.stdin.readline def ..