[BOJ] 2025 실골랜디
Gold Random Defense
💻250101~250131 (골5~골2)
1. 창영이와 퇴근 (골4) 22116
다익스트라
다익스트라는 INF로 배열을 만든 후 더 작은 값이 있으면 갱신해준다.
visited 필요 없는 이유: height[x][y]가 c보다 작으면 이미 방문을 한 것이므로 height로 방문 여부를 대체 할 수 있다.
A[nx][ny]로 가는 최대 경사를 구한 후 new_cost가 현재 height[nx][ny]보다 작으면 갱신한 후 heap에 넣는다.
2. 시간낭비 (골2) 30464
DP
a[i]이 0이면 같은 공간에 계속 갈 수 있다. 이때 예외처리를 해주어야 한다.
1)앞으로, 2)뒤로, 3)앞으로 가면서 dp 계산을 해주는데 최댓값으로 계속 갱신하면 된다.
3. 최소비용 구하기 (골5) 1916
다익스트라
전형적인 다익스트라 문제이다.
answer에는 누적된 값이 들어가기 때무에 INF를 100,000이 아니라 매우 큰 수로 초기화해야 한다.
최소 힙에 (가중치, 출발지)을 넣는다. 이미 최솟값이면 연산을 건너뛴다. 아니라면 graph에서 도착지를 찾아 갱신 해준 후 힙에 넣는다.
4. 백도어 (골5) 17396
다익스트라
A[i]가 0인 곳만 갈 수 있으므로 26, 27번째 줄을 추가해준다.
나머지는 다익스트라 코드와 동일
5. 미로만들기 (골4) 2665
다익스트라
검정을 만나면 가중치를 +1 해준다.
가중치가 현재 값보다 작으면 갱신한 후 힙에 추가한다.
6. 호석이 두 마리 치킨 (골5) 21278
플로이드 워셜
Dijkstra: 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
Floyd Warshall: 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
주의할 점: 음수 간선은 없고 자기 자신 노드로 가는 최솟값이 0이기 때문에 미리 0으로 초기화해줘야 한다.
임의 두 개의 행을 뽑아 각 열 최솟값들의 합으로 total을 만든다. 왕복이므로 그 total의 두 배가 답이 된다.
플로이드 워셜 출력 결과
9223372036854775807 0 2 1 3 3
9223372036854775807 2 0 1 1 1
9223372036854775807 1 1 0 2 2
9223372036854775807 3 1 2 0 2
9223372036854775807 3 1 2 2 0
(건물1, 건물2, 최솟값 배열, total) 출력 결과
1 2 [0, 0, 1, 1, 1] 3 # 정답: 1 2 6
1 3 [0, 1, 0, 2, 2] 5
1 4 [0, 1, 1, 0, 2] 4
1 5 [0, 1, 1, 2, 0] 4
2 3 [1, 0, 0, 1, 1] 3
2 4 [2, 0, 1, 0, 1] 4
2 5 [2, 0, 1, 1, 0] 4
3 4 [1, 1, 0, 0, 2] 4
3 5 [1, 1, 0, 2, 0] 4
4 5 [3, 1, 2, 0, 0] 6
7. 알고스팟 (골4) 1261
다익스트라
백도어와 풀이 동일
8. 특정한 최단 경로 (골4) 1504
다익스트라
시작하는 곳으로 다익스트라 결과 배열을 생성한 후 거기서 종료 지점을 인덱스로 추출해서 쓸 수 있다.
따라서 answer를 return하고 종료 지점을 바꿔가며 result를 구하면 된다.
9. 네트워크 복구 (골2) 2211
다익스트라
answer는 [C, A, B]인 배열이다.
new_C가 원래 answer C보다 작으면 answer의 값을 갱신하고 힙에 추가한다.
최종 answer 2부터 N까지의 [A, B]을 출력하는 문제이므로 K는 무조건 N-1이 된다.
K > N-1: 최소 개수를 복구하는 것이 아니다.
K < N-1: 작으면 1번 컴퓨터에서 도달할 수 없는 존재한다. 이는 문제 조건과 맞지 않는다.("통신 가능하도록 복구한다.")
10. 입국심사 (골5) 3079
이분탐색
현재 mid로 T[i]를 나눈 몫을 다 더해서 그것이 M보다 크거나 같으면 answer를 갱신한다.
11. 타임머신 (골4) 11657
벨만포드
음의 간선이 포함된 상황에서도 사용 가능, 음수 간선 순환을 감지할 수 있다.
모든 간선을 모든 노드만큼 확인한다. → O(VE)
다익스트라와 다르게 모든 간선을 순회하기 때문에 start와 이어져 있는지 판단하기 어렵다.
따라서 if문에 'dist[cur] != INF'을 추가하여 start와 이어져 있는 곳의 노드만 갱신할 수 있다.
마지막 노드에서도 값이 갱신된다면 음수 순환이 존재하는 것이다.
12. 웜홀 (골3) 1865
벨만포드
출발 지점이 정해져있지 않기 때문에 음수 순회가 존재하면 "YES"를 출력한다.
그렇게 때문에 dist[start]를 초기화하지 않아도 되고, "!=INF"라는 조건이 없어도 된다.
13. 중량제한 (골3) 1939
다익스트라
지금까지 경로의 최소 중량을 구한다.
그 최소 중량이 dist[도착노드]보다 크다면 dist를 갱신하고 힙에 추가한다.
dist는 최대한 큰 값이어야 하므로 최대힙으로 구한다. 즉, a노드로 가는 새로운 중량이 dist[a]보다 작으면 갱신하기 않아도 된다.
💡 핵심은 중량 최소의 최대를 구하는 것
💻250301~250331 (골5~골2)
1. 1학년 (골5) 5557
DP
0~20까지이기 때문에 dp를 Nx21로 정의하고 풀면 된다.
이전까지의 개수를 현재 dp에 계속 더해서 푸는 방식이다.
[예제 입력 1] dp 출력 결과
11
8 3 2 4 8 7 2 4 0 8 8
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 0, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 2, 0, 3, 0, 3, 0, 4, 0, 2, 0, 3, 0, 1, 0, 2, 0, 1]
[2, 0, 3, 0, 4, 0, 5, 0, 4, 0, 6, 0, 4, 0, 6, 0, 3, 0, 3, 0, 1]
[4, 0, 6, 0, 8, 0, 10, 0, 8, 0, 12, 0, 8, 0, 12, 0, 6, 0, 6, 0, 2]
[8, 0, 12, 0, 8, 0, 12, 0, 10, 0, 12, 0, 10, 0, 10, 0, 8, 0, 12, 0, 8]
10
2. 1, 2, 3 더하기 5 (실1) 15990
DP
1, 2, 3 개수를 저장하는 배열이 있어야 하므로 2차원 dp이다.
연속된 숫자가 나오면 안 되므로 dp[i][1]은 dp[i-1][2]와 dp[i-1][3]을 더한 값이다.
마찬가지로 dp[i][2]는 i-2번째의 1과 3을 더한 값이다.
숫자가 나타내는 것은 무엇일까? 가지치기의 첫 번째 숫자이다.
4는 (1,3), (1,2,1), (3,1)로 나타낼 수 있다.
이때 1로 시작하는 것이 2개, 3으로 시작하는 것이 1개라서 dp[4]가 [2, 0, 1]이 되는 것이다.
dp[10]까지 출력
0 [0, 0, 0, 0]
1 [0, 1, 0, 0]
2 [0, 0, 1, 0]
3 [0, 1, 1, 1]
4 [0, 2, 0, 1]
5 [0, 1, 2, 1]
6 [0, 3, 3, 2]
7 [0, 5, 2, 2]
8 [0, 4, 5, 3]
9 [0, 8, 7, 6]
10 [0, 13, 7, 7]
3. 트리와 쿼리 (골5) 15681
트리+DP
트리와 DP를 합친 문제이다. 즉, size가 DP가 되는 것
1. makeTree로 childNode를 저장하는 배열을 만든다.
2. countSubtreeNodes로 현재 노드의 서브 트리 노드 개수를 size에 저장한다.
※ 리프 노드부터 계산하며, 자식size+1로 계산하는 것을 알 수 있다.
[예제 입력 1] currentNode와 size 출력 결과
5
4
3
1
1 [0, 1, 0, 1, 1, 1, 0, 0, 0, 0]
2
2 [0, 1, 1, 2, 1, 1, 0, 0, 0, 0]
3 [0, 1, 1, 3, 1, 1, 0, 0, 0, 0]
4 [0, 1, 1, 3, 4, 1, 0, 0, 0, 0]
6
7
7 [0, 1, 1, 3, 4, 5, 1, 1, 0, 0]
9
9 [0, 1, 1, 3, 4, 5, 2, 1, 0, 1]
8
8 [0, 1, 1, 3, 4, 5, 3, 1, 1, 1]
6 [0, 1, 1, 3, 4, 5, 4, 1, 1, 1]
5 [0, 1, 1, 3, 4, 9, 4, 1, 1, 1]
4. 트리 노드 합의 최댓값 (골4) 25515
트리+DP
트리와 DP를 합친 문제이다.
1. 단방향 그래프이기 때문에 graph는 자식만 갖고 있다.
2. 리프 노드부터 돌면서 "현재 노드"와 "현재 노드+자식 노드" 중 큰 수를 현재 노드로 갱신한다.
※ 리프 노드부터 계산하며, 자식size+1로 계산하는 것을 알 수 있다.
[예제 입력 1] dp 출력 결과
[1, -5, 0, -1, 0, 0, 0, 0]
[1, -5, 0, -1, 10, 0, 0, 0]
[1, 5, 0, -1, 10, 0, 0, 0]
[6, 5, -10, -1, 10, 20, 0, 0]
[6, 5, 10, -1, 10, 20, -5, 20]
[6, 5, 10, -1, 10, 20, 15, 20]
[6, 5, 25, -1, 10, 20, 15, 20]
[31, 5, 25, -1, 10, 20, 15, 20]
5. 사회망 서비스(SNS) (골3) 2533
트리+DP
트리와 DP를 합친 문제이다.
1. dp가 1이면 얼리 아답터이고, 0이면 얼리 아답터가 아니다. 초깃값은 0이다.
2. 자식 노드를 보면서 자식 모든 노드가 얼리 아답터이면 부모는 얼리 아답터가 아니라. 자식 노드 중 하나라도 얼리 아답터가 아니면 부모는 얼리 아답터가 된다.
3. 그 계산은 "max(1-dp[node], dp[current])"이다. 0이 하나라도 있으면 "1-dp[node]"에 의해 dp[current]는 1이 되고, 한 번 1이 되면 max 함수가 있어 계속 1이 된다.
[예제 입력 1] dp 출력 결과
• 5, 6 -> 2가 얼리 아답터됨
• 3 -> 1이 얼리 아답터됨
• 7, 8 -> 4가 얼리 아답터됨
[0, 1, 1, 0, 1, 0, 0, 0, 0]
[예제 입력 2] dp 출력 결과
• 7, 8, 9 -> 4가 얼리 아답터됨
• 2 -> 1이 얼리 아답터됨
• 5, 6 -> 3이 얼리 아답터됨
[0, 1, 0, 1, 1, 0, 0, 0, 0, 0]
6. 공통 부분 문자열 (골5) 5582
DP
1. 투포인터로도 풀 수 있는 문제이다.
2. 문자열 중 짧은 것을 s1, 긴 것을 s2로 두고, s1을 반복문 돌린다.
3. 현재 dp는 최소 이전 dp 값과 같으므로 갱신을 해준다.
4. 현재 dp만큼 이전 문자열부터 현재 문자열까지가 s2에 있다면 현재 dp를 증가시킨다. 즉, i가 5이고 dp[i]가 3이면 s1[2:5]가 s2에 있는지 확인하는 것이다.
[예제 입력 1] dp 변화
[1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0] -> A
[1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0] -> AB
[1, 2, 3, 3, 0, 0, 0, 0, 0, 0, 0] -> ABR
[1, 2, 3, 3, 3, 0, 0, 0, 0, 0, 0]
[1, 2, 3, 3, 3, 3, 0, 0, 0, 0, 0]
[1, 2, 3, 3, 3, 3, 3, 0, 0, 0, 0]
[1, 2, 3, 3, 3, 3, 3, 4, 0, 0, 0] -> CADA
[1, 2, 3, 3, 3, 3, 3, 4, 4, 0, 0]
[1, 2, 3, 3, 3, 3, 3, 4, 4, 5, 0] -> ADABR
[1, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5]
7. 문제 추천 시스템 Version 1 (골4) 21939
힙+딕셔너리
1. 최솟값, 최댓값 출력은 힙, 값 탐색 및 삭제는 딕셔너리를 활용한다.
2. 입력을 배열로 받아 힙, 딕셔너리에 넣어준다. 이 배열은 참조되어 있기 때문에 한 곳에서 바뀌면 다른 곳에서도 바뀐다.
3. 힙은 (정렬 조건, 배열)로 넣어주고, 딕셔너리는 "entry[문제번호] = 배열"로 하여 문제 번호로 탐색할 수 있게 한다.
1. recommend: 최댓값 또는 최솟값 출력이다. 이때는 힙을 사용하므로 top이 REMOVED로 표시가 되어있다면 pop을 해주고 heap[0]을 출력한다.
2. add: 새로운 값을 추가한다. 아직 pop되지 않은 문제가 heap에 남아있어도 참조값이 다르기 때문에 덮어씌워지지 않는다.
3. solved: entry[문제번호][0]를 REMOVED로 체크한다. 그러면 heap에 있는 해당 참조값의 e[0]도 REMOVED로 표시된다. 이때 삭제된 문제에 대해 다른 난이도로 입력이 다시 들어온다면 entry는 덮어씌워진다.그렇지만 값만 바뀌는 것이 아니라 참조가 바뀌게 되어 heap의 새로운 입력을 가리키게 된다.
💡 e[0]이 숫자라면 REMOVED 상수 값도 숫자여야 한다. 문자열이면 타입 에러가 뜬다.
[예제 입력 1] entry 변화
add 1402 59
{1000: [1000, 1], 1001: [1001, 2], 19998: [19998, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
recommend 1
19998
{1000: [1000, 1], 1001: [1001, 2], 19998: [19998, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
solved 1000
{1000: [0, 1], 1001: [1001, 2], 19998: [19998, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 1000 제거: entry[1000][0]이 0으로 바뀜
solved 19998
{1000: [0, 1], 1001: [1001, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 19998 제거: entry[19998][0]이 0으로 바뀜
recommend 1
1402
{1000: [0, 1], 1001: [1001, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
recommend -1
1001
{1000: [0, 1], 1001: [1001, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
solved 1001
{1000: [0, 1], 1001: [0, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 1001 제거: entry[1001][0]이 0으로 바뀜
recommend -1
2667
{1000: [0, 1], 1001: [0, 2], 19998: [0, 78], 2667: [2667, 37], 2042: [2042, 55], 1402: [1402, 59]}
-> 2667 제거: entry[2667][0]이 0으로 바뀜
8. 양팔저울 (골3) 2629
DP
배낭 문제 일종, "1학년" 문제와 비슷하다.
1. 각 추가 i이며 dp 계산을 하기 전에 dp[i][무게]=1 처리를 해준다.
2. 이전 dp 값이 1이면 현재 dp도 1로 갱신해준다.
3. 그 후 무게를 더하고 뺀 절댓값이 범위 안에 들어온다면 1로 갱신해준다.
[예제 입력 2] dp 변화
2 [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
3 [0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0]
3 [0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0]
3 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
💻250401~250430 (실2~골2)
1. 컵라면 (골2) 1781
힙
1. 입력 받는 힙: (데드라인 오름차순, 컵라면 내림차순)
2. 정답 구하는 힙: (컵라면 오름차순)
3. answer의 길이는 현재 데드라인을 절대 넘을 수 없다.
4. answer의 길이와 데드라인이 같다면 answer의 최솟값(answer[0])과 현재 컵라면 수를 비교한 후 더 큰 것으로 바꾼다.
2. 알약 (골5) 4811
DP
1. 알약 온전한 한 개를 꺼내는 경우의 수 생각한다.
2. dp[3]을 예시로 생각해보자. 맨 앞 W와 맨 뒤 H는 고정이므로 가운데 4개에서 W가 들어갈 위치를 생각하면 된다.
WWWHHH, WWHWHH -> 앞에 두 개를 선택: dp[2]*dp[0]
WWHHWH -> 앞에 하나 뒤에 하나 선택: dp[1]*dp[1]
WHWWHH, WHWHWH -> 뒤에 두 개를 선택: dp[0]*dp[2]
3. 뮤탈리스크 (골4) 12869
DP+BFS
1. 3개를 동시에 확인해야 하므로 3차원 dp로 둔다.
2. 최솟값을 구해야하므로 INF로 초기화하고 시작값을 0으로 한다.
3. (0, 1, 2)가 될 수 있는 모든 순열을 구해서 모든 damage 경우를 구한다. 해당 dp가 최소로 갱신될 때 q에 넣는다.
4. x, y, z가 모두 0이 되면 해당 dp가 공격 횟수이므로 반환한다.
4. 안녕 (실2) 1535
DP
💡 배낭 문제 팁: 기쁨을 구하는 것이면 dp[i][j]는 기쁨 합이 된다. (행-입력 받은 배열, 열-체력(제한된 숫자임))
13줄: j가 현재 체력보다 작으면 현재 기쁨을 추가할 수 없기 때문에 dp[i-1][j]를 그대로 현재 dp에 넣는다.
15줄: 현재 체력만큼 왔으면 현재 기쁨을 넣을 수 있다. 단, 넣는 것(dp[i-1][j-L[i]]+J[i])과 안 넣는 것(dp[i-1][j]) 중 뭐가 더 큰지 판단해야 한다.
dp[i-1][j-체력]+기쁨 vs 이전 dp 값
5. 게임 (골2) 1103
백트래킹+DP
현재 위치에서 최대 얼만큼 갈 수 있는지 백트래킹으로 구하고 dp로 메모이제이션한다.
사이클 구하는 방법: 백트래킹을 돌고 있는데 방문한 곳을 또 방문했다면 사이클이 있는 것
백트래킹이기 때문에 visited를 0으로 초기화해준다.
6. 자두나무 (골5) 2240
DP
j가 짝수일 때는 무조건 1에 위치하고, 홀수일 때는 무조건 2에 위치하기 때문에 3차원이 아니라 2차원 dp로 해도 괜찮다.
pos(위치): j가 짝수면 1에 위치, 홀수면 2에 위치
get(자두 받을 수 있는지): 자두 떨어지는 위치와 현재 pos가 같으면 1, 다르면 0
j가 0이면 이전 값에 get을 더한다.
dp[i-1][j]: 안 움직였을 때, dp[i-1][j-1]: 이전에서 이동해서 지금 위치에 왔을 때
[예제 입력 1] dp 출력 결과
0 1 2
[0, 0, 0]
2 [0, 1, 0]
1 [1, 1, 2]
1 [2, 1, 3]
2 [2, 3, 3]
2 [2, 4, 3]
1 [3, 4, 5]
1 [4, 4, 6]
7. 비밀 모임 (골4) 13424
플로이드워셜
자기 자신으로 가는 경우는 0으로 초기화한다.
특정 장소에서 모든 친구들에게 가는 거리의 합이 최소일 때 그 장소가 답이다.
8. 선수과목 (Prerequisite) (골5) 14567
DP+위상정렬
위상 정렬: 순서가 정해져있는 작업
indegree: 진입 차수
진입 차수가 0인 것을 다 큐에 넣고, pop을 하면서 indegree를 다시 계산해준다.
이때 indegree가 0이 되는 노드가 있으면 다시 큐에 넣는다.
9. 지름길 (실1) 1446
DP
1. 현재 위치가 지름길 끝나는 지점: min(원래 값, 지름길 이용x, 지름길 이용o)
2. 아닌 지점: min(원래 값, 지름길 이용x)
10. 달력(골5) 20207
IMOS
1. "빨리 시작 + 늦게 끝남"으로 정렬한다. 그래야 빈틈없이 채워지고, imos를 적용할 수 있다.
2. imos로 채운 후 연속으로 0이 아닐 때 width*height로 답을 구한다.
11. 주사위 윷놀이 (골2) 17825
브루트포스+시뮬레이션
1. 점수가 10, 20, 30이면 각각 score[1], score[2], score[2]로 넘어간다.
2. 말 0, 1, 2, 3의 모든 순열을 구하여 브루트포스를 돌린다.
1. 이미 도착한 말이 또 선택되면 return
2. 말의 새로운 위치를 구한다.
3. 도착(42)면 위치만 이동시키고 점수에 더하지 않는다.
4. 판에 있는 모든 말과 비교한다. 자기 말이면 continue
5. 위치가 같으면 return
6. 현재 말과 비교하는 말이 모두 x, y가 0보다 클 때 25, 30, 35이면 return
7. 왜냐하면 22와 30은 점수만 같고 위치가 다를 수 있기 때문이다.
💻250501~250531 (골2)
1. 환승 (골2) 5214
BFS
모든 역을 인접리스트로 하면 최대 1000^3이 되어 메모리 초과가 된다.
따라서 하이퍼튜브 자체도 [1, 2, 3]과 연결되어 있는 정점이라고 생각하면 풀면 된다.
예제 1에서 N이 9이므로 10부터 14는 하이퍼튜브 정점이라고 생각하면 아래와 같이 나온다.
1 [10, 11]
2 [10]
3 [10, 12]
4 [11]
5 [11, 13]
6 [12, 13, 14]
7 [12, 13]
8 [14]
9 [14]
10 [1, 2, 3]
11 [1, 4, 5]
12 [3, 6, 7]
13 [5, 6, 7]
14 [6, 8, 9]
각 정점을 가는 것은 개수에 추가되어야 하지만 그것을 잇는 하이퍼튜브는 개수에 추가되면 안 되므로 23번 째 줄을 조건문을 넣어준다.
2. 춘배가 선물하는 특별한 하트 (골5) 30408
집합
1. N과 M이 같다면 바로 return
2. n이 짝수면 2로 나눈 값을 넣고, 홀수면 2로 나눈 값의 몫과 +1을 넣는다.
3. 집합으로 처리하기 때문에 s의 길이는 최대 2이다.
4. 1만 남아서 num에 들어가는 숫자가 하나도 없을 때까지 while을 돈다. s에 M이 있다면 바로 return
3. 곡예 비행 (골4) 21923
DP
1. 상승 DP: 왼쪽 아래에서 시작, 오른쪽 위에서 끝
2. 하강 DP: 오른쪽 아래(도착 지점)에서 시작, 왼쪽 위에서 끝
3. 각 지점에서 두 개 DP 합이 가장 큰 곳이 정답이다.
4. 시간 관리하기 (골5) 6068
그리디+정렬
1. T, S를 입력 받고 S 큰 순, T 큰 순으로 정렬
2. 이전 계산에서 구한 날짜와 현재 s 중 작은 값에서 t를 뺀다.
3. 예를들어 이전 계산에서 구한 날짜가 5이고, 현재 t와 s는 2, 6이면 6에서 2를 빼는 것이 아니라 5에서 2를 빼야하는 것이다.
4. 이때 뺀 값이 0보다 작아지면 -1을 return하며 종료한다.
5. 사과나무 (골5) 19539
그리디
1. 사과나무 높이 합이 3의 배수가 아니면 바로 종료한다.
2. 물을 한 번 줄 때마다 2+1이나 3+0으로 자란다. 따라서 2의 개수가 1의 개수보다 크거나 같으면 YES이다.
3. 짝수로 나눈 몫은 2의 개수, 홀수인 개수는 1이다.
4. 예를들어 2 / 7 / 9는 2 / 2, 2, 2, 1 / 2, 2, 2, 2, 1을 의미하고 2의 개수가 1의 개수보다 많으니 YES이다.
6. A를 B로 (골4) 13019
그리디
1. 문자 개수가 다르다면 바로 return
2. 뒤에서부터 검사한다. 그 이유는 옮기는 문자보다 뒤에 있는 문자열은 순서가 바뀌지 않기 때문이다.
초깃값은 start=0, end=N-1이다. 뒤에서부터 비교하며 같으면 end를 감소시켜 다음으로 넘어가고, 다르면 해당 문자를 앞으로 던져 start를 증가시킨다.
1. 예제 1을 보면 마지막 C와 A가 다르기 때문에 C를 앞으로 던진다. 결과: ABC -> [C]AB
2. 이때 C는 계산을 끝낸 것이기 때문에 start를 1 증가시킨다.
3. [C]AB와 CBA를 비교했을 때 마지막 B와 A가 다르기 때문에 B를 앞으로 던진다. 결과: [C]AB -> [BC]A
4. 이때 B도 계산을 끝낸 것이기 때문에 start를 1 증가시켜 end와 같아지며 계산을 종료한다.
※ B, C 순서가 아닌 C, B 순서로 넘기는 이유
순서가 상관없다. 앞으로 보낼 문자열을 고르기만 하면 던져지고 알아서 정렬된다고 생각하면 된다.
ABC -> [C]AB -> [BC]A인데 원래 문자에서 A[B][C]를 골라 앞으로 던진 것으로 생각하면 된다. 두 개를 던졌으니 답은 2이다.
7. 빚 (골5) 10427
그리디
추가적으로 갚아야할 돈 = 고른 것 중에서 가장 많은 돈을 빌렸을 때 빌린 돈 x M - 고른 돈들 합
S(M) = max(고른 돈들)*M - sum(고른 돈들)
1. S(M)이 최소가 되기 위해서는 고른 돈들이 max(고른 돈들)에 최대한 가까워야 한다.
2. 즉, 정렬을 한 후 최댓값을 정한 다음 그 인덱스부터 -M까지를 고른 돈으로 계산하면 된다.
예제 1에서 [1, 3, 4, 5, 8]로 정렬한 후 M은 3일 때, [1, 3, 4], [3, 4, 5], [4, 5, 8]만 누적합으로 계산하면 시간을 단축시킬 수 있다.
이 때 [3, 4, 5]가 5에 가장 가까운 수들로 되어 있기 때문에 이때 S(3)이 3이 된다.
8. 우유 도시 (골4) 14722
DP
3차원 DP로 많이 풀지만 2차원 DP로도 풀 수 있다.
1. 무조건 0 -> 1 -> 2 순서로 마셔야 한다.
2. 지금까지 우유를 0번 마셨다면 0번 우유를 마셔야 할 차례고, 4번 마셨다면 1번 우유를 마셔야 할 차례인 것이다.
3. dp[i][j]는 현 도시까지 마신 우유 최대 개수다.
4. 만약 dp[i][j]가 4라면 arr[i][j]가 1일 때 즉, dp[i][j]%3 == arr[i][j]일 때 1 증가시킨다.
[예제 입력 1] dp 출력 결과
1 2 3 3
2 2 3 3
3 3 3 3
4 4 5 5
[예제 입력 2] dp 출력 결과
1 2 2 2 2
2 3 3 3 3
3 4 5 6 7
4 4 5 7 8
5 5 5 8 9
9. 갤러리 (골5) 2115
구현
1. X인 곳은 [북, 남, 서, 동]에 . 이 있는지 확인한다. 그 결과를 result에 저장한다.
2. 북이 1이라면 오른쪽의 북도 1인지 확인한다. 남도 똑같다.
3. 서가 1이라면 아래쪽의 서도 1인지 확인한다. 동도 똑같다.
10. 움직이는 미로 탈출 (골3) 16954
구현
arr를 시계 방향 90도 돌린 chess 배열을 만들어 (0, 0)에서 시작해서 (7, 7)에서 끝날 수 있게 했다. 돌린 이유는 벽을 큐를 사용해서 움직이게 하고 싶었기 때문이다.
1. 현재 캐릭터 위치를 수집한다.
2. 각 캐릭터를 이동시킨다. visited에 체크해둔다.
3. 큐를 사용하여 벽을 왼쪽으로 한 칸씩 이동시킨다.
4. 벽에 위치한 캐릭터를 죽인다. visited를 0으로 만들어 다음 반복문에서 수집되지 않게 한다.
빠른 계산과 무한 루프 방지를 위해 캐릭터가 없다면 0, 벽이 없다면 1을 early return 한다.
11. 돌 굴러가유 (골4) 23889
그리디+정렬
1. total에 [각 돌이 부실 수 있는 모래성 개수, 돌 위치]를 추가한다.
2. answer에는 total을 개수 큰 것, 위치 작은 것으로 정렬한 후 앞에서부터 M개만큼 추가한다.
3. 사전순으로 가장 빠른 답을 출력해야 하므로 answer를 오름차순 정렬한 후 출력한다.
💻250601~250630 (골5~골2)
1. 모래성 (골2) 10711
구현
1. result 배열은 현재 위치의 주변 무너진 곳 개수를 저장한 값이다. 이것이 모래성 튼튼함 정도보다 크거나 같다면 큐에 담는다.
2. q개수 만큼 for문을 돌면서 무너뜨리고(arr[x][y] = 0) 주변 result를 하나씩 증가시킨다.
3. 증가시킨 곳에서 새롭게 무너질 곳인지 확인하고 있다면 큐에 넣는다.
4. visited는 이미 무너진 곳이면 새롭게 계산하면 안 되므로 추가한다.
1. 모래성 (골2) 16472
투포인터
1. start는 시작하는 위치 end는 끝나는 위치, [start:end+1]이 현재 보고 있는 문자열이다.
2. 문자 개수가 N보다 작거나 같다면 answer를 갱신하고, end를 하나 증가시킨다.
3. 증가시킨 end도 visited 계산을 한 후 새로운 문자열이 들어왔다면 cnt를 +1 한다.
4. 반대로 cnt가 N보다 크다면 visited를 다시 계산하고 사라지는 문자가 있다면 cnt를 -1 한다.
2. 사과나무 (골5) 20002
누적합
우선 각 위치의 누적합을 구한다.
2. [i][j]의 누적합은 "바로 위의 누적합" + "바로 왼쪽의 누적합" - "왼쪽 위까지 누적합"에 현재 값을 더하면 된다.
그렇게 누적합을 만든 후 부분 정사각형 합(검정색)을 구하는 방법은 아래와 같다.
검정 = 빨강 - 파랑 - 연두 + 보라
보라 부분이 두 번 빠지므로 나중에 한 번 더해서 부분 누적합을 구한다.
3. 두 개의 탑 (골5) 2118
투포인터
1. 입력 받은 거리를 누접합으로 계산해 위치로 바꾼다.
[1, 2, 3, 4, 5] -> [1, 3, 6, 10, 15]
mid는 원형의 절반이므로 값이 나올 수 있는 최대이다.
start, end를 0, 1로 잡고 매번 answer를 계산한다.
거리가 mid보다 작다면 end를 증가시키고, mid보다 크다면 start를 증가시켜 거리를 좁힌다. 같다면 바로 return 시켜 시간을 줄인다.
4. 성곽 (골3) 2234
비트마스킹, DFS, 그래프
1. [1, 2, 4, 8]이 [서, 북, 동, 남]으로 주어지기 때문에 값을 이진수로 변경하고 (1 << k)와 비교하여 True면 1 증가시킨다.
2. 해당 방향에 벽이 없다면 같은 덩어리로 간주하여 인덱싱한다.
3. 같은 덩어리 번호끼리 더하여 각 덩어리 번호의 합을 구한다.
4. 인접한 두 개의 위치를 보고 다른 덩어리라면 두 덩어리 합으로 answer를 갱신한다.
5. 마지막에 idx가 하나 더 증가하므로 -1을 한 값을 출력한다.
댓글남기기