본문 바로가기

분류 전체보기115

[BOJ/PYTHON] 1448. 삼각형 만들기 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/1448 문제 요약 빨대 N개 중 3개를 선택했을 때, 세 변의 길이 합의 최댓값 핵심 아이디어 길이 합의 최대값을 구해야 하기 때문에 빨대 길이 리스트를 큰 것부터 정렬하면 된다. 삼각형은 제일 큰 변의 길이가 나머지 두 변의 길이 합보다 작을 때 성립하는데, 그 정의를 이용하면 된다. 큰 것부터 정렬된 상황이기 때문에, list[i] > list[i + 1] + list[i + 2]가 성립하면 된다. 순차 3개(a b c)가 성립 안 하면 a b d, a b e... 등의 케이스도 성립 불가해 저렇게만 보면 된다. 마지막 세 개까지 봤는데도 성립 안 하면 -1을 출력하면 된다. 풀이 # silver3-1448. 삼각형 만들기 .. 2023. 5. 18.
[BOJ/PYTHON] 11656. 접미사 배열 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/11656 문제 요약 문자열의 모든 접미사 사전순 정리 후 출력 핵심 아이디어 접미사 리스트를 저장해두고 그거를 정렬한 걸 출력하면 된다. 예시의 baekjoon 접미사 리스트는 baekjoon을 첫 번째부터 두 번째, 세 번째…로 자르면 된다. 풀이 # silver4-11656. 접미사 배열 # 문자열의 모든 접미사 사전순 정리 후 출력 s = input() #문자열 S list = [] # 접미사 리스트 for i in range(len(s)): list.append(s[i:]) print(*sorted(list), sep='\\n') 실행 시간 메모리 31256KB, 시간 44ms (python3) 2023. 5. 18.
[BOJ/PYTHON] 11582. 치킨 TOP N (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/11582 문제 요약 치킨 집 정렬하고자 함 N/2명이 차례대로 2개의 치킨집을 선택해 정렬 → N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택하여 치킨집 정렬 → 계속해서 N/8명, N/16명이 정렬을 진행 → 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력 핵심 아이디어 n, k 둘다 2의 거듭제곱이라 n을 k로 나눈 몫만큼 숫자를 자를 수 있다. k명이 정렬하면 전체 치킨집 개수인 n을 k만큼 나눈 n // k 개씩 나눠서 정렬하게 된다. 그만큼 끊어서 각각 정렬하고 이어붙여 출력하면 된다. 풀이 # sil.. 2023. 5. 18.
[BOJ/PYTHON] 1431. 시리얼 번호 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/1431 문제 요약 시리얼번호 정렬한 결과 출력 길이 짧은 것부터 길이 같으면 자리수 합 작은 것부터 (숫자만 더함) 사전순. 숫자가 알파벳보다 사전순으로 작음. 핵심 아이디어 정렬 기준이 여러 개이기 때문에 정렬 기준에 해당하는 애를 순서대로 커버해주면 된다. 정렬 우선순위에 따라 새 리스트에 길이, 자리수 합, 시리얼 번호를 넣어주고, 그것을 정렬하면 된다. 풀이 # silver3-1431. 시리얼 번호 import sys input = sys.stdin.readline # 1. 길이 짧은 것부터 # 2. 길이 같으면 자리수 합 작은 것부터 (숫자만 더함) # 3. 사전순. 숫자가 알파벳보다 사전순으로 작음. n = int(i.. 2023. 5. 18.
[BOJ/PYTHON] 2423. 전구를 켜라 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/2423 문제 요약 N × M 직사각형 크기의 전자 회로에서 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결 전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜짐 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값 구하기 핵심 아이디어 불가능할 경우 "NO SOLUTION”을 출력해야 하는데, N + M이 홀수인 경우 물리적으로 불을 켜는 것이 불가능하다. 다익스트라로 푼다고 가정했을 때 비용값을 구하는 것이 필요한데, ‘돌려야 하는 칸의 개수의 최솟값’을 구해야 하기 때문에 돌릴 필요가 없으면 0, 돌려야 하면 1로 비용을 산정하면 된다. “/”일 때는 (i, j+1)에서 (i+1, j) 방향으.. 2023. 5. 18.
[BOJ/PYTHON] 9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/9694 문제 요약 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하기 친밀도: (최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]) 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력, 최고의원을 만날수 없는 경우엔 -1을 출력 핵심 아이디어 ‘관계’가 사람과 사람 간 관계라는 것을 고려했을 때, 사람(정치인)은 정점, 관계는 간선으로 보면 된다. 친밀도의 정도가 정해져있으므로 친밀도를 거리 값으로 간주, 다익스트라 알고리즘으로 풀면 된다. 풀이 # gold3-9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 import sys, h.. 2023. 5. 16.

티스토리툴바