728x90 🤖 알고리즘/백준 문제풀이8 [파이썬] 3011 이름 지어주기 (백준) 1. 문제 설명 문제 : 3011 - 이름 지어주기 https://www.acmicpc.net/problem/3011 사용 언어 : 파이썬 (Pypy3) 문제요약 : 구간 [A, B]에 들어있는 수 중에서 수열들의 각 수들 중 가장 차이가 큰 홀수를 구하여라. 2. 문제 풀이 해설 : 우리는 기본적으로 2가지의 경우를 생각해 볼 수 있다. 첫 번째 경우는 기존의 수들 중에 답이 있는 것이다. 이 경우에는 아들들의 이름을 정렬시킨 후, i번째 수와 i+1번째 수의 중간으로 구할 수 있었다. 이는 (P[i]+P[i+1])/2로 구할 수 있다. 두 번째 경우는 A+1 혹은 B-1중 답이 있는 것이다. 이 경우에는 모든 아들들과의 거리 중 가장 짧은 거리를 비교하여 답을 구할 수 있었다. 아들이 최대 100명이.. 2024. 2. 20. [파이썬] 18185 라면사기 Small (백준) 1. 문제 설명 문제 : 18185 - 라면 사기 (Small) https://www.acmicpc.net/problem/18185 사용 언어 : 파이썬 (Pypy3) 문제요약 : 하나는 3원, 연속된 2개는 5원, 연속된 3개는 7원으로 라면을 구매 할 수 있을 때 라면을 구하는 최소 비용을 구하여라. 2. 문제 풀이 해설 : 케이스로 나누어서 풀 수 있다. 여기서는 대표적으로 2가지의 케이스로 나누어서 설명하겠다. i+1의 값이 i+2보다 클 때의 경우이다. 이 때에는 먼저 연속된 2개를 처리하고, 연속된 3개를 처리한다. i+1의 값이 i+2보다 작을 때의 경우이다. 이 때에는 먼저 연속된 3개를 처리하고, 연속된 2개를 처리한다. 만약 위에 두 경우에서 i번째 값이 가장 커서 남게 된다면, 마지막.. 2024. 2. 14. [파이썬] 28218 격자 게임 (백준, KOI 1차) 1. 문제 설명 문제 : 28218 - 격자 게임 https://www.acmicpc.net/problem/28218 사용 언어 : 파이썬 (Pypy3) 문제요약 : NM의 보드에서 말이 아래로 한 칸, 오른쪽으로 한 칸, 오른쪽 아래 대각선 방향으로 1~K칸 움직일 수 있다. 두 명의 사람이 돌아가면서 말을 NM의 위치로 옮긴다고 할 때, 말의 시작 위치에 따라 누가 NM칸으로 옮길 수 있는지 구하시오. 2. 문제 풀이 해설 : N, M, K가 다 300 이하이기 때문에 300^3으로 쉽게 구할 수 있습니다. 거꾸로 보며 갈 수 있는 곳에 Lose (무조건 질 수밖에 없는 칸)가 하나라도 주어진다면 Win (무조건 이길 수밖에 없는 칸)으로 표시합니다. 갈 수 있는 곳이 모두 Win이라면 Lose로 표.. 2024. 2. 14. [파이썬] 1219 오민식의 고민 (백준) 1. 문제 설명 문제 : 1219 - 오민식의 고민 https://www.acmicpc.net/problem/1219 사용 언어 : 파이썬 (Pypy3) 문제요약 : 각 거리마다 잃는 돈과 얻는 돈이 주어질 때, 최대로 갖게 될 수 있는 돈을 구하라. 이때, 도착을 못하는 경우나 돈을 무한히 많이 가질 수 있는 경우라면 각각 gg와 Gee를 출력하라. (이 문제를 풀면서 오민식보다 더 심한 고민에 빠졌었다.) 2. 문제 풀이 해설 : 일반적인 벨만포드를 사용한다. 이때, 사이클이 존재하는지를 알기 위해 bfs를 사용하였다. 또한 얻을 수 있는 돈과 잃어야 하는 돈이 각각 주어짐으로 해당 구간에서 얻을 수 있는 돈을 미리 구해두었다. 코드 : import sys; input = sys.stdin.readl.. 2023. 12. 31. [파이썬] 1738 골목길 (백준) 1. 문제 설명 문제 : 1738 - 골목길 https://www.acmicpc.net/problem/1738 사용 언어 : 파이썬 (Pypy3) 문제요약 : 각 거리마다 얻거나, 빼앗길 수 있는 금품의 양이 주어졌을 때, 최대의 금품을 갖게 될 수 있는 경로를 구하여라. 알고리즘 : 벨만-포드 2. 문제 풀이 해설 : 일반적인 벨만포드를 이용하여 구할 수 있다. 이때 고려해야 할 점이 몇 가지 있다. 1. 최소 가중치를 찾는 벨만포드와는 다르게, 최대 가중치를 구해야 하므로 distance를 -inf로 초기화해야 한다. (이에 따라 조건식을 조금 바꾸어야 한다.) 2. 중요한 경로 구하기!! 각 노드마다 그 전의 노드를 구해놓아 마지막에 최단 경로를 구한다. 코드 : import sys; input =.. 2023. 12. 31. [파이썬] 1865 웜홀 (백준) 1. 문제 설명 문제 : 1865 - 웜홀 https://www.acmicpc.net/problem/1865 (골3) 사용 언어 : 파이썬 (Pypy3) 사용 알고리즘 : 벨만-포드 알고리즘 문제요약 : M개의 양방향 간선인 도로와 W개의 단방향 간선인 웜홀이 이들을 지나는 시간과 함께 주어졌을 때, 음의 사이클이 있는지 구하여라. 2. 문제 풀이 해설 : 음의 사이클을 찾을 수 있는 벨만포드 알고리즘을 이용한다. 여기서 주의해야 할 점이 있는데, 일반 벨만포드 코드와 다르게 아래 코드를 삭제해야 한다. distance[now_node] != INF 왜냐하면 위 코드는 'start'라는 지점에서부터 연결된 각 노드까지의 최단 경로를 구하는 코드이다. 하지만 이 문제에서는 시작 지점이 주어지지 않고, 음의.. 2023. 12. 28. [아희] 7787 빨간 칩, 파란 칩 (백준) 1. 문제 설명문제 : 7787 - 빨간 칩, 파란 칩 https://www.acmicpc.net/problem/7787 사용 언어 : 아희 (아희로 플레 풀었다!) 문제요약 : A와 B가 돌아가면서 빨간 칩 혹은 파란 칩 k개를 책상에서 제거하여 마지막 칩을 가져가는 게임을 할 때, 승자가 누구인지 구하시오. 2. 문제 풀이풀이 : 스프라그-그런디 정리를 이용한다. 먼저 그런디 수를 찾는다. 이때 그런디 수는 칩 개수를 2로 나누었을 때 나머지가 1이면 1이고, 4로 나누었을 때 나머지가 4면 2이고, 나머지 경우에는 그런디수가 3이다. 빨간 칩의 개수와 파란 칩의 개수의 그런디 수를 XOR 해서 0이 아니면 A가 이기고, 아니면 B가 이긴다. 즉 빨간 칩과 파란 칩의 그런디수가 같다면 B가 이기고, .. 2023. 8. 19. [파이썬] 17404 RGB거리 2 (백준) 문제 : 17404 - RGB거리 2 https://www.acmicpc.net/problem/17404 사용 언어 : 파이썬 (Pypy3) 문제 요약 : 서로 이웃하는 집과 첫 번째 집과 N 번째 집의 색이 같지 않다고 했을 때, 집의 색깔을 RGB로 칠하는 최소의 비용을 구하라. 해설 : 첫 집의 색깔을 정하고 (for문으로 다 해보기), 배열에 전 자신의 색깔을 제외한 두 색의 가격을 비교하여 최솟값을 자신에게 더하고 반복한다. 코드 : import sys input = sys.stdin.readline #입력 N = int(input()) arr = [list(map(int,input().split())) for i in range(N)] m = (1000+1)*N ans = [m, m, m] f.. 2022. 7. 23. 이전 1 다음 728x90
