안녕

0. 문제 링크 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 1. 풀이 방법 투포인터 주석에도 적어놓았듯이, k^2 - (k-1)^2의 값이 n보다 크게 되는 순간 더 이상 해당 값은 볼 필요가 없음 따라서 n - 1까지만 투포인터로 보기로 했고, 이때 n이 1, 2인 순간은 오류가 발생하는데 해당 값은 아래의 while 문에서 해결함 아무튼 1 ~ n - 1까지의 값을 모두 제곱하여 리스트에 넣어놓았음 maps[right] - maps[left]를 했을..

0. 문제 링크 https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 1. 풀이 방법 현재까지의 누적합 값을 구함. 해당 누적합 값 - k의 값이 딕셔너리에 존재한다면 개수만큼 정답에 더하면 됨 0이 들어갈 수도 있으므로 누적합 값이 키로 있는 딕셔너리 값도 계속해서 업데이트해줘야 함 2. 코드 import sys input = sys.stdin.readline def bf(): c..

0. 문제 링크 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 1. 풀이 방법 다익스트라 구글에 일요일 아침의 데이트 파이썬을 검색하면 나오는 풀이와 흡사하게 풀었음. 일단 검은 방은 전처리로 10,000으로 설정하였음. 최대 50 * 50이 맵 사이즈가 되기 때문에 2500 이상으로 설정하면 됨. 이후 힙을 이용한 다익스트라로 목적지까지 최소 거리를 구하면 됨 최종적으로 목적지에는 검은 방 * 10,000 + 흰 방 * 1의 값이 저장되는데..

0. 문제 링크 https://www.acmicpc.net/problem/1596115961번: 회전 초밥첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net2023.05.15 - [Computer Science/알고리즘] - [백준 - Python] 2531 - 회전 초밥 [백준 - Python] 2531 - 회전 초밥0. 문제 링크 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d,..

0. 문제 링크 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 1. 풀이 방법 4개씩 투포인터로 범위를 잡는다. set으로 만든 후에, 중복되지 않는 개수를 센다. 만약 행사로 주는 쿠폰에 해당하는 번호가 없으면, 1을 더해서 개수를 센다. 마지막으로 '회전 초밥' 이므로, 맨 뒤에서 맨 앞까지 먹는 경우도 계산해야 한다. 해당 코드는 매우 느리다. 최적화 작업은 하지 않았다. 통과는 된다. 아래는 내가..

0. 문제 링크 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 1. 풀이 방법 예전 알고리즘 시간에 풀었던 문제라 비교적 간단하게 풀 수 있었음 2022.04.15 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 - 연쇄 행렬곱셈 (Chained Matrix Multiplication) 예전에 내가 쓴 글을 보면 자세히 설명해 놓았음 키 포인트는 i ~ i + dia까지의 최적을 구하기 위해서는 i ~ ..

0. 문제 링크 https://www.acmicpc.net/problem/22945 22945번: 팀 빌딩 능력치가 다 다른 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같 www.acmicpc.net 1. 풀이 방법 정렬할 필요 없음. 정렬을 한다면, 각 개발자의 인덱스도 따로 저장해놔야 함. 결론적으로 인덱스도 맞춰서 계산해야 하므로, 굳이 할 필요가 없음 투 포인터로 양 측 끝부터 시작했음 min 값을 수정해야 하므로, min 값이 되는 포인터를 옮겼음 만약 두 개의 값이 같다면 둘 다 옮겼음. 해당 문제의 경우 하나의 포인터만 옮겨도 정답이 맞음. 다만 하나의 포인터..

0. 문제 링크 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 1. 풀이 방법 중복 제거를 위하여 세트로 정렬한다. 각 번호의 인덱스가 압축된 좌표의 번호가 된다. 그대로 출력하면 끝 2. 코드 import sys input = sys.stdin.readline if __name__ == "__main__": n = int(input()) maps = list(map(int, input().s..

0. 문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 풀이 방법 0으로 끝나는 숫자와 1로 끝나는 숫자를 구분한다. i 자리의 숫자는 i - 1 번째 어떤 숫자든 0을 붙여도 상관없다. i 자리의 숫자는 i - 1 번째 숫자에서 끝이 0으로 끝나는 숫자에만 1을 붙일 수 있다. 이런 점화식을 세운 후 문제를 풀면 끝 조금 더 최적화를 위해서 메모리를 2*2만 사용하였다. 실제 메모리 사용은 줄어들지 않았는데, 이유는 ..

0. 문제 링크 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 풀이 방법 투 포인터로 풀었음 (투 포인터로 안 풀어도 됨) 이를 위하여 눈덩이를 크기 순서대로 정렬하였음 우선 엘사의 범위는 for문을 이용하여 구하였음 엘사의 눈사람의 길이가 정해지면, 투포인터를 이용하여 안나의 눈사람의 길이를 구함 만약 엘사 > 안나라면 안나의 눈사람이 커져야 하므로 left += 1 하였음 만약 엘사 < 안나라면 안나의 ..