본문 바로가기
728x90

알고리즘316

[python] 백준 12919 A와 B 2 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제 해결 처음에 S->T로 만드는 BFS 함수를 생각했다. 하지만 메모리초과, 시간초과 나오는 것을 보고 다른방법을 생각하게 되었다. 이전에 긴 문자열에서 짧은 문자열을 만드는 풀이가 생각이 났다. 역시 문자열을 만드는 것은 긴 문자열에서 짧은 문자열로 생각하는 것이 정답이다.(그래야 비교할 경우의 수가 줄어든다.) CODE S = str(input()).. 2023. 4. 5.
[python] 백준 1422 숫자의 신 https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 www.acmicpc.net 문제 해결 모든 수는 1번 이상씩 사용 하지만 더 사용하는 숫자는 오직 하나이고 가장 큰 수일 것이다.(이유는 첫번째는 자리수가 크기 때문이고 두번째는 자리수가 같으면 앞에 큰수가 오는 것이 큰수이기 때문에 많이 사용할 수록 좋다.) 따라서 가장 큰 수를 변수로 저장한 다음 n-k 만큼 추가적으로 리스트 안에 저장하면 된다. 문제는 숫자 배열이다. 모든 숫자는 $10^{9}.. 2023. 4. 5.
[python] 백준 9576 책 나눠주기 https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 문제 해결 어떤 범위를 가진 학생한테 먼저 책을 줄지 생각을 해야한다. 범위길이가 작은 사람부터 해결하는 것이 좋다.(가능한 경우의 수가 적으므로) 그러면 right upperbound는 작을수록, left lowerbound는 클 수록 먼저 해결하는 것이 좋다. CODE from collections import deque for _ in range(int(input())): n, m = map(i.. 2023. 4. 5.
[python] 백준 2583 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 해결 사각형으로 영역을 막아놓고 나머지 빈 구역의 개수를 구하고 각 영역의 크기를 구하면 되는 문제 bfs를 이용해 영역을 메우면서 쉽게 풀 수 있다. CODE from collections import deque def bfs(x,y): global visited que = deque() que.append((x,y)) visited[y][x] = 1 cnt = 1 dx.. 2023. 4. 4.
728x90