본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 3986 좋은 단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제 해결 중요한 것은 좋은 단어가 될려면 단어 안의 모든 알파벳이 짝을 만들어 아치형 곡선을 만들 수 있어야 하며 모두 겹치지 않아야 한다는 것이다. 왼쪽부터 오른쪽으로 단어의 알파벳을 보면서 짝이 없는 것을 stack안에 쌓아 놓고 만약 stack[-1]과 알파벳이 같으면 같이 아치형 곡선을 만들면 되므로 stack.pop()으로 짝을 이루고 사라지게 한다. 만약 단어 끝까지 보고나서 stack안에 쌓인.. 2023. 7. 10.
[python] 백준 21610 마법사 상어와 비바라기 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제 해결 순서대로 구현하면 어렵지 않은 문제 구름의 좌표를 모은 다음 주어진 방향, 주어진 크기만큼 이동해서 비를 +1씩 내려준다. 이 때 동시에 일어나도 모두 같은방향, 같은 크기만큼 가기 때문에 구름이 겹칠 일이 없다. 비가 내린 곳에서는 물복사를 할 거기 때문에 좌표를 리스트를 만들어 저장한다. 구름은 이제 모두 없고 물복사 할 곳 좌표에 차례대로 물복사를 한다. 이 때는 동시에 일.. 2023. 7. 9.
[python] 백준 21609 상어 중학교 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 문제 해결 놓치기 쉬운 조건들을 먼저 잘 인지하고 있어야한다. 블록 그룹은 연결된 블록 집합이며 일반 블록이 적어도 한개 이상 있어야하며 색은 모두 같아야한다.(무지개는 무조건 포함가능) 연결된 블록이 가장 많은 블록 집합을 골라야한다. 만약 같은 것이 존재한다면 무지개색이 가장 많은 것을 선택하며 그래도 같으면 기준 블록 행이 가장 큰 것, 그래도 같으면 기준 블록 열이 가장 큰 것을 고르는.. 2023. 7. 8.
[python] 백준 2159 케익 배달 https://www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 문제 해결 케익을 받는 순서는 정해져 있다. 케익을 받을 수 있는 위치는 모두 4가지이다. 그래서 출발점-도착점에 따른 최소거리를 각각 구해야한다. 받는 위치가 다르면 다음 순서에 영향을 줄 수 있기 때문 이를 구현하기 위해 가장 좋은 것은 DP이다. dist[i][j] 는 i번째 사람 케익을 받을 때 동(j=0),서(j=1),남(j=2),북(j=3),(아래 코드는 +중앙(j=4))에.. 2023. 7. 7.
728x90