전체 글
-
[BOJ] 2482번 - 색상환Algorithm/BOJ 2022. 6. 13. 22:15
[BOJ] 2482번 - 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 연속되어 있는 색은 추가가 불가능 단계별 갯수를 세가면서 추가 -> DP DP를 나타낼 때 DP[i][j] 시 i는 색의 갯수 / j는 색을 고를 수 있는 경우이다. 1. i가 1인 경우에는 모두 n의 갯수에 맞추어 증가한다. 2. 후에 i가 2부터는 경우의 수를 나타내다 보면 DP[i][j] = DP[i-1][j-2] + DP[i][j-1] 로 계산식이 되는 것을 알 수 있다...
-
[BOJ] 1700번 - 멀티탭 스케줄링Algorithm/BOJ 2022. 6. 13. 22:07
[BOJ] 1700번 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 알고리즘 그리디 알고리즘 멀티탭을 오랫동안 유지하고 싶음으로 가장 나중에 사용할것을 바꾸어주는게 좋다. 1. 멀티탭에 이미 있는 경우 -> PASS 2. 멀티탭에 빈자리가 있는 경우 -> 빈자리에 꼽는다. 3. 멀티탭에 있는것을 뺀 다음 새롭게 꼽는다. 4. 단 멀티탭에 있는 것을 빼기 위해서는 다음에 사용하지 않을 것이 우선순위 5. 다음에 사용된다면 가..
-
[BOJ] 2473번 - 세 용액Algorithm/BOJ 2022. 6. 11. 14:27
[BOJ] 2473번 - 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 알고리즘 각 용액의 3가지의 합이 최소가 되는 경우의 수를 찾아야한다. 이분탐색을 이용하여 하나를 선택한 다음에 나머지 두가지를 매칭하는 방법을 사용하였다. 1. 데이터를 입력 받는다. 2. 이분 탐색을 위하여 데이터를 정렬한다. 3. 각 용액 별로 최소의 경우(left , right 를 두어 결과 값이 0보다 크면 right를 작게 반대는 ..
-
[BOJ] 11660번 - 구간 합 구하기 5Algorithm/BOJ 2022. 6. 11. 14:00
[BOJ] 11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 알고리즘 구간 합을 미리 DP로 구하여 둔 다음에 해당되는 행 영역의 합을 구하여준다. 계산상 편의를 위해 2차원은 N+1로 적용하였다. 코드 #BOJ 11660번 import sys input = sys.stdin.readline answer = [] n , m = map(int,input().split()..
-
[BOJ] 2170번 - 선 긋기Algorithm/BOJ 2022. 6. 11. 13:56
[BOJ] 2170번 - 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 주의할 점이 선을 긋는다고 하여 0부터 시작하는 것이 아닌 음수부터 시작이 된다 및 여러 번 그은 부분이나 한번 그은 부분이나 동일하게 계산되어야 한다. 알고리즘 그리디 알고리즘을 이용하여 풀었다. 시작점이 작은 좌표부터 시작하여 가장 긴 값을 찾아가는 형태로 찾아가면 최소 최대 길이를 구할 수 있다. 최소 값을 갱신하면서 찾아야 하기..
-
[BOJ] 2143번 - 두 배열의 합Algorithm/BOJ 2022. 6. 10. 14:47
[BOJ] 2143번 - 두 배열의 합 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 알고리즘 해당 범위 내에서 특정 값이 있는지 여부를 확인하기 위한 이분탐색 ( 정렬 필수 ) 1. A,B 각각의 경우의 수로 나타낸다. 2. B를 정렬한다. 3. A를 통해 B에서 해당되는 경우의 수가 있는지 이분탐색 4. 결과 출력 코드 #BOJ 2143번 import bise..
-
[BOJ] 15903번 - 카드 합체 놀이Algorithm/BOJ 2022. 6. 10. 14:11
[BOJ] 15903번 - 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 알고리즘 그리디로 생각하여 풀었다. 작게 만들기 위해서는 작은 두수를 뽑아내서 갱신시켜주어야 한다. 이때 시간 복잡도가 가장 낮은 Heap을 이용 1. heapq를 이용하여 Data 초기화 2. 요청받은 갯수만큼 heapq 갱신 3. 갯수 출력 코드 #BOJ 15903번 import heapq n , m = map(i..
-
[BOJ] 1520번 내리막 길Algorithm/BOJ 2022. 6. 10. 13:07
[BOJ] 1520번 내리막 길 처음에는 DP와 BFS로 푸는 문제로 접근하였다. 생각하였던 예시 중에서는 올바르게 동작하였으나, 제출 시 시간 초과가 걸려 실패하였다. 왜 그런지 곰곰히 생각해보던 도중 BFS로 구현을 하게 되면 순차적으로 탐색을 하게 되어 돌아서 가는 경우에 대해서 갱신하여 처리하기 어렵다. 따라서 어차피 숫자 가중치에 따라 더 큰것부터 우선으로 찾아 들어가야하기 때문에 BFS의 Queue를 우선순위 Queue로 구현해볼까라고 생각하였다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는..