본문 바로가기
728x90

알고리즘316

[python] 백준 18310 안테나 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 문제 해결 최소거리를 구하는 공식이 있을까? 우선 원점(0)에 가까운 순서대로 집 위치를 놓아야 할 것 같다. 안테나 설치 위치를 $x_{i}$라 하자. 그러면 안테나부터 거리의 합은 $\left| x_{1}-x_{i} \right| + . . . \left|x_{i-1}-x_{i}\right| + \left|x_{i+1}-x_{i}\right| + . . . \left|x_{n}-x_{i}\right|$이다. 이 때 .. 2023. 3. 18.
[python] 백준 10026 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 해결 그래프를 만들어 구역을 나누는 개수를 세는 문제 적록색약인 사람은 'R' 과 'G'를 같은 색으로 본다. bfs()를 이용하면 금방 풀 수 있는 문제 (DFS도 좋지만 이렇게 이동하는 문제는 BFS가 편한 것 같습니다.) 사실 두 번 사용하는거 말고 다른 방법이 있나 생각을 해봤지만... 글쎄...? CODE import sys from collections import dequ.. 2023. 3. 18.
[python] 백준 12904 A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 해결 bfs를 이용해 S에서 두 경우의 수를 이어 붙인 문자열을 다시 que에 넣어가며 T가 나올 수 있는지 찾을려고 했다. 하지만 나타날 수 있는 문자열의 경우의 수가 너무 많아 메모리 초과가 떴다. 역으로 생각하여 T에서 S로 만드는 과정을 생각했다. 경우의 수도 역으로 생각해 뒤에 'A'이면 'A'를 떼고 que에 넣고 'B'면 'B'를 떼고 문자열.. 2023. 3. 18.
[python] 백준 16194 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 해결 i개를 사는 방법의 수는 매우 많다. 하지만 i개를 사는 방법의 가지수는 (1개 사는 방법+i-1개 사는방법) + (2개 사는 방법 + i-2개 사는 방법).... + i개 통째로 사는 방법으로 나타낼 수 있다. dp[i]를 i개 사는 최소 비용이라 하자. dp[i] = dp[i-j] + P[j]로 나타낼 수 있다. (j=1,2,3,4,...i) P[j]는 j개를 묶음으로 살 때 비용 CO.. 2023. 3. 18.
728x90