[python] 백준 1049: 기타줄

[python] 백준 1049: 기타줄 1049번: 기타줄 (acmicpc.net) 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 실버 4 그리디 접근 먼저 기타줄의 브랜드가 여러개가 입력되었다면, 낱개 값의 가장 싼 값과 한팩 값의 가장 싼 값을 입력한 리스트로부터 골라낼 수 있어야 한다. 골라낸 두 값을 가지고 다음의 분기를 결정한다. 기타줄 낱개 가격 * 6 < 기타줄 팩이라면 무조건 낱개로만 기타줄을 사는게 싸게 친다. 그런데 기타줄 팩 하나를 사는게 더 이득이라면 최대한 기타줄 팩으로 많이 구입..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 9.
• textsms

[python] 백준 10610 : 30

[python] 백준 10610 : 30 10610번: 30 (acmicpc.net) 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 실버 5 그리디 접근 N의 입력값 크기나 너무나 크기 때문에 안의 숫자들을 어떻게 바꿔야할지 고민이 많았는데 그냥 다음의 조건들을 참고하면 쉽게 풀 수 있었다. N이 3의 배수임을 확인하는 법 : 각 자릿수의 총합이 3의 배수면 N은 3의 배수이다. 30의 배수를 찾아야 하기 때문에 N의 숫자 중에 0이 없으면 -1을 출력하도록 한다. 두 조건을 만족하는 숫자는 순서를 바꾸어도 3..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 7.
• textsms

[python] 백준 1697 : 숨바꼭질

[python] 백준 1697 : 숨바꼭질 1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버 1 그래프, BFS 접근 일차원으로 이동할 수 있는 bfs문제이다. 5를 노드라고 생각했을 때, 5가 탐색할 수 있는 노드는 4, 6, 10이된다. 각각의 노드는 [3, 5, 8], [5, 7, 12], [9, 11, 20]을 탐색할 수 있을 것이다. 여기서 미리 방문했던 노드는 방문하지 않도록 해야하며 노드가 일차원 이동을 하기 때문에 문제..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 3.
• textsms

[python] 백준 1325 : 효율적인 해킹(BFS)

[python] 백준 1325 : 효율적인 해킹(BFS) 1325번: 효율적인 해킹 (acmicpc.net) max_hack: max_hack = h hack.append([i, h]) for i, cnt in hack: if cnt == max_hack: print(i, end = ' ') 어차피 1번부터 n번까지의 노드를 돌아가면서 bfs를 돌리기 때문에 나오는 순서대로 최댓값에 해당하는 노드를 출력하면 된다.

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 2.
• textsms

[python] 백준 1743 : 음식물 피하기(BFS)

[python] 백준 1743 : 음식물 피하기(BFS) 1743번: 음식물 피하기 (acmicpc.net) 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 실버 1 그래프, BFS 접근 이차원 배열을 사용하여 그래프를 구성하고 좌표를 한칸씩 이동하면서 음식물의 크기를 계산한다. bfs탐색이 끝나면 해당 음식물의 크기에 대한 계산이 끝난 것과 같으므로 각 bfs탐색의 반환값중 가장 큰 값을 출력하도록 한다. 코드 import sys; input = sys.stdin.r..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 28.
• textsms

[python] 백준 18352 : 특정 거리의 도시 찾기(BFS)

[python] 백준 18352 : 특정 거리의 도시 찾기 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 실버 2 그래프, BFS 접근 단방향 그래프 구현과 특정 정점으로부터의 거리를 구현할 수 있으면 쉽게 풀 수 있는 문제이다. 코드 import sys; input = sys.stdin.readline from collections import deque def bfs(no..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 27.
• textsms