본문 바로가기
728x90

알고리즘316

[python] 백준 9625 BABBA https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 해결 A→B, B→BA로 바뀌고 k번째 바뀌었을 때 A, B의 개수를 구하는 것이므로 DP를 이용하는 것이 편할 것이란 생각이 든다. dp[i][0]는 i번 눌렀을 때 A의 개수, dp[i][1]은 i번 눌렀을 때 B의 개수로 정의한다. dp[0][0] = 1, dp[0][1] =0 에서 시작 dp[i][0] = dp[i-1][1] 이고 dp[i][1] = dp[i-1][0] + dp[i-1][.. 2023. 3. 17.
[python] 백준 2810 컵홀더 https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 문제 해결 컵홀더와 사람과의 일대일 대응을 만들면 된다. stack을 이용해 남는 컵홀더와 컵홀더가 없는 사람을 저장해서 대응을 맞추면 될 것이다. 대응을 못맞추는 사람을 hurdle이라는 변수를 통해 인원수를 저장한다. n에서 hurdle을 빼면 끝 CODE import sys input = sys.stdin.readline n = int(input()) seats = list(input().rstrip()) stack = [0] hurdle = 0 while seats: x = seats.p.. 2023. 3. 17.
[python] 백준 2212 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 해결 처음에 문제 이해하는데 오랜 시간이 걸렸다. '각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. ' 가 주요 문장이다. 이 말은 수신 가능 영역을 open set(열린 집합)으로 나타낼 것인데 그 길이의 합을 물어보는 것이다. 그려면 너무 간단하게 이웃과 거리 n-1개 중 길이가 긴 k-1개를 집중국과 다른 집중국과의 거리로 생각하.. 2023. 3. 17.
[python] 백준 9506 약수들의 합 https://www.acmicpc.net/problem/9506 9506번: 약수들의 합 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라. www.acmicpc.net 문제 해결 완전수의 가장 클 수 있는 약수는 n%2==0일 때 n//2 따라서 1부터 n//2+1까지 for문을 통해 나눠 떨어지는 수를 찾는다. 더해서 n이 나오면 완전수이다. 표현은 n,=은 각각 sep=' '로 출력하고 ' + '.join을 통해 더하기를 표현할 수 있다. 아니면 N is NOT perfect. 나오도록 출력 CODE import sys input = sys.stdin.. 2023. 3. 16.
728x90