[BOJ]2024 골랜디
Gold Random Defense
💻240226~240303 (골5~골4)
1. 암호 만들기 (골5) 1759
백트래킹
check[0]은 모음 개수, check[1]은 자음 개수
백트래킹이므로 재귀가 끝나면 visited[i] = 0으로 초기화 시켜주기
2. 알파벳 (골4) 1987
DFS, 백트래킹
alphabet은 지금까지 어떤 알파벳을 지났는 지 저장하는 배열
재귀를 나오면 visited와 alphabet 배열을 둘다 초기화시켜야 된다.
💻240304~240310 (골1)
1. 달이 차오른다, 가자. (골1) 1194
비트마스킹+BFS
비트마스킹을 쓰는 이유: 열쇠를 갖는 가짓수가 총 64가지가 있는데 이걸 반복문으로 현재 어떤 키를 가지고 있는지 찾으면 시간초과가 난다.
만약 a, d 키가 있으면 0b1001, 즉 9이기 때문에 visited[x][y][9]=1이 된다.
※ key에 바로 갱신하는 것이 아닌 new_key를 쓰는 이유
그 방향으로 가지 않았는 데도 key값이 갱신되어버린다. 소문자를 만나지 않는다면 그냥 key를 인자로 넘겨줘야한다.
💻241209~241215 (골4)
1. 지뢰찾기 (골4) 2140
그리디, 구현
네 방향을 일차원으로 생각하고 각각에서 changeMine 함수를 호출한다.
changeMine은 무엇이 들어올지 모르니 8방향을 다 탐색하면서 "*"이거나 "#"일 때만 처리한다.
"*": 이미 채워져 있으므로 지뢰 개수를 늘린다.
"#": 지뢰 개수가 적힌 숫자와 이미 동일하면 그 곳엔 지뢰가 무조건 없어야 하므로 " "를 채운다. 아직 지뢰 개수와 적힌 숫자가 동일하지 않다면 지뢰가 있어야 하므로 "*"를 채운다.
중앙은 지뢰가 채워지지 않은 상태("#")로 남을텐데 최대 지뢰 개수를 출력하면 되므로 이 부분도 지뢰라고 가정하고 답을 구하면 된다.
2. 강의실 (골4) 2140
그리디, 정렬, 우선순위 큐
종료 시간, 시작 시간 오름차순으로 정렬한 후
제일 빨리 끝나는 강의 종료 시간이 현재 강의 시작 시간보다 작거나 같으면 pop한 후 현재 강의 종료 시간을 push하고
크면 새로운 강의실 생성이므로 push만 한다.
3. 수열의 점수(골4) 2036
그리디, 정렬
1은 그냥 더할 때가 최적의 경우이므로 입력 받을 때 바로 더해준다.
0은 음수가 홀수개일 때만 필요하므로 몇 개 있는지 중요하지 않다. 있으면 0으로 바꾸고 없으면 1로 해주어 zero를 바로 곱할 수 있게 했다.
음수는 오름차순 정렬하고, 양수는 내림차순 정렬하여 앞에서부터 두 개씩 곱하여 더해주고 홀수개면 마지막 수는 그냥 더한다.
4. 색종이(골4) 2590
그리디, 구현
6번 색종이는 한 장이 곧 한 판이다.
5번 색종이는 한 장으로 한 판을 채우면 11개 칸이 남고 이것을 1번 색종이로 채울 수 있다.
4번 색종이는 한 장으로 한 판을 채우면 20개 칸이 남고 2번 색종이 5개로 최대한 채운 후 남은 칸을 1번 색종이로 채울 수 있다.
3번 색종이는 네 장으로 한 판을 채울 수 있다. 이때 주의해야할 점은 3번 색종이가 1장 있으면 2번 색종이는 6장이 아닌 5장 밖에 못 붙인다는 점이다. two_count 배열이 3번 색종이 개수 별 2번 색종이 최대 개수이다.
2번 색종이는 9장으로 한 판을 채울 수 있고 남은 칸은 1번 색종이로 채울 수 있다.
1번 색종이는 36장이 한 판이고 남은 색종이가 있으면 answer에 더해준다.
💻241223~241231 (골5~골2)
1. 졸려(골5) 9519
구현
while문을 돌면서 i와 N이 같아지면 출력한 후 종료한다.
그게 아니면 answer 배열에 현재 문자열을 넣은 후 반복되는 문자열이 있는 순간 반복문을 빠져나온다.
N을 answer의 길이로 나눈 나머지를 출력한다.
2. 같이 눈사람 만들래?(골3) 20366
투 포인터
오름차순 정렬 후 엘자의 눈덩이를 O(N^2)로 먼저 구해준다.
엘자의 눈덩이 사이에서 안나의 눈덩이 두 개를 투 포인터로 구한다.
0일 때는 바로 답을 출력한 후 종료하고 아닐 때는 최솟값을 계속 갱신해준다.
3. 구간 자르기(골2) 2238
투 포인터, IMOS
imos 배열은 구간이 시작할 때 +1, 구간이 끝날 때 -1을 해서 만든다.
[2, 0, 0, 2, 0, 0, 0, 0, -1, 0, -2, 0, 0, 0, 0, -1]
그 다음 위 배열을 누적값으로 재계산한다.
[2, 2, 2, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 0]
while문에서 total이 K보다 작으면 imos[B]를 total에 더해주며 B를 1 증가시키고,
total이 K보다 크면 imos[A]를 total에서 빼며 A를 1 증가시킨다.
4. 램프(골4) 2238
애드 혹
스위치를 홀수번 누르면 바뀐 상태, 짝수번 누르면 그대로인 상태다.
"001"이면 0, 1열을 홀수번 누르고 2열을 짝수번 누르면 되는데 "홀수+홀수+짝수"는 무조건 짝수이며, K가 짝수일 때만 이 스위치가 "켜진 상태"가 될 수 있다.
반대로 "011"이면 0열을 홀수번 누르고 1, 2열을 짝수번 누르면 되는데 "홀수+짝수+짝수"는 무조건 홀수가 된다.
이 특징으로 절대 "켜진 상태"로 만들 수 없는 행을 찾을 수 있다.
1. 0의 개수가 K보다 많은 경우
2. 0의 개수가 K와 홀짝이 안 맞는 경우
켜진 상태를 만들 수 있는 행과 같은 상태인 행 개수를 센 후 가장 많은 개수인 것이 답이 된다.
초깃값이 다른 상태끼리는 아무리 스위치를 조작해도 둘다 켜진 상태로 만들 수 없기 때문이다.
5. ZOAC(골5) 16719
재귀
제일 작은 것을 찾은 이후로는 그것의 뒤쪽에서 작은걸 계속 찾아야 사전순으로 가장 작다.
right를 먼저 재귀를 돌린 후 left를 재귀 돌리면 된다.
start는 재귀 배열의 시작점으로 start+idx를 하면 원래 string의 idx가 나온다.
6. 압축(골4) 1662
스택
answer는 문자 길이이다.
"33(562(71(9)))"의 문자 길이는 "1+3(2+2(1+1(1)))"이다.
※ answer는 이전 answer에서 더하는 것이 아니라 새로운 괄호 안에서 계속 갱신되는 값이다.
"(": stack에 [더할 문자 길이, 곱하는 값]을 저장한다. 현재 answer에서 곱하는 값을 따로 넣어주므로 answer-1을 하여 stack에 저장하면 된다. 새로운 괄호가 열렸으니 answer는 0으로 초기화한다.
")": 마지막 stack을 꺼내 계산한다. top[0]은 문자 길이이므로 더해주고, top[1]은 괄호 안의 문자 길이(=answer)에 곱해준다.
숫자: answer에 1을 더해준다.
예제 입력 1
33(562(71(9)))
S[i]= 3 stack= [] answer= 1
S[i]= 3 stack= [] answer= 2
S[i]= ( stack= [[1, 3]] answer= 0
S[i]= 5 stack= [[1, 3]] answer= 1
S[i]= 6 stack= [[1, 3]] answer= 2
S[i]= 2 stack= [[1, 3]] answer= 3
S[i]= ( stack= [[1, 3], [2, 2]] answer= 0
S[i]= 7 stack= [[1, 3], [2, 2]] answer= 1
S[i]= 1 stack= [[1, 3], [2, 2]] answer= 2
S[i]= ( stack= [[1, 3], [2, 2], [1, 1]] answer= 0
S[i]= 9 stack= [[1, 3], [2, 2], [1, 1]] answer= 1
S[i]= ) stack= [[1, 3], [2, 2]] answer= 2
S[i]= ) stack= [[1, 3]] answer= 6
S[i]= ) stack= [] answer= 19
19
예제 입력 6
1()66(5)
S[i]= 1 stack= [] answer= 1
S[i]= ( stack= [[0, 1]] answer= 0
S[i]= ) stack= [] answer= 0
S[i]= 6 stack= [] answer= 1
S[i]= 6 stack= [] answer= 2
S[i]= ( stack= [[1, 6]] answer= 0
S[i]= 5 stack= [[1, 6]] answer= 1
S[i]= ) stack= [] answer= 7
7
7. 이모티콘(골4) 14226
BFS
v: 화면에 있는 이모티콘 수
board: 클립보드에 있는 이모티콘 수
answer: 시간
visited는 이차원 배열로 해야한다. v와 board값이 둘 다 다르면 다른 경우이기 때문이다.
댓글남기기