[BOJ] 12월 1주차
BOJ 16939: 2×2×2 큐브
Link : https://www.acmicpc.net/problem/16939
소스 코드
solution
구현 문제. 설명은 간단하지만 과정은 녹록치 않다.
간단하게 표현할 방법이 떠오르질 않아 하드코딩을 했다. (인덱스 규칙을 찾기가 힘들었다)
큐브를 돌릴 수 있는 방향은 총 12가지가 존재하는데 이 12가지를 구현해주면 되고
큐브를 돌렸을 때 어디서 어디로 이동하는지 잘 체크해 놓는다면 푸는데 그렇게 어렵지는 않다.
구현의 난이도보다는 귀찮음이 더 컸던 문제.
BOJ 2306: 유전자
Link : https://www.acmicpc.net/problem/2306
solution
DP 문제.
f(l, r) : [l, r]에서 얻을 수 있는 KOI 유전자의 최대 길이
s[l], s[r]이 각각 a, t 또는 g, c일 때 2씩 카운트할 수 있도록 해주고
어느 위치에서 분할될지 모르니 모든 경우에서 분할해 재귀를 돌려주자.
BOJ 16681: 등산
Link : https://www.acmicpc.net/problem/16681
solution
집과 고려대학교의 높이가 1이다. 그리고 목표 지점은 보다 높은 위치에 있어야 하므로 1보다 커야 한다.
때문에 TC 2번에서는 Impossible을 출력해야 한다. 그럼 이제 그렇지 않은 경우는 다익스트라로 풀 수 있다.
지점 u, v가 있고 거리가 w라고 하자. 또한 u, v는 목표 지점의 후보이다. 이 때 각 지점의 높이를 h[u], h[v]라 정의하면
문제에서는 양방향 경로라고 쓰여있지만 어차피 목표 지점까지는 높이가 증가하는 방향으로만 이동해야 하므로
h[u] > h[v]일 땐 u->v 경로만, h[u] < h[v]일 땐 v->u 경로만 추가해줘야 한다.
만약 목표 지점이 u로 확정됐다고 하자. 그럼 1번(집)에서 목표지점까지 높이가 증가하는 방향으로 이동해서 도착 후
N번(고려대학교)까지 높이가 감소하는 방향으로 이동해야 한다.
목표 지점 -> 고려대학교가 높이가 감소하는 방향이라면, 고려대학교 -> 목표 지점까지는 높이가 증가하는 방향으로 가야한다.
때문에 집과 고려대학교에서 다익스트라를 돌려준 후 목표 지점의 후보가 되는 지점을 모두 탐색하면서
등산의 가치가 최대일 때를 취하면 된다.
등산의 가치는 음수가 될 수 있으므로 0이 아닌 -INF로 해줘야 한다.
일반적으로 쓰는 INF 값(예 987654321)보다 등산의 가치가 커질 수 있으므로
int형이 아닌 long long으로 바꿔놓고 INF값도 더 크게 설정해주자.
BOJ 17144: 미세먼지 안녕!
Link : https://www.acmicpc.net/problem/17144
solution
구현 문제. 이것도 제출 수가 심상치 않아서 찾아보니 삼성 SW 기출문제였다.
그래도 다른 문제에 비해서 구현 난이도가 높지는 않은거 같다.
문제 설명이 잘 돼있어서 딱히 주의할 점도 떠오르지 않고.. 설명에 충실하게 구현하자.
BOJ 14728: 벼락치기
Link : https://www.acmicpc.net/problem/14728
solution
DP 문제.
남은 시간에 필요한 시간을 쓸 수 있냐 없냐로 나눠서 쓸 수 있다면 점수를 더해주자.
BOJ 2186: 문자판
Link : https://www.acmicpc.net/problem/2186
solution
DP 문제다.
기본적으로 길찾는 BFS 문제처럼 상하좌우로 움직일 수 있다. (K배로 움직일 수도 있다)
찾으려는 문자열의 인덱스를 인자로 두어서 찾아야 하는 알파벳을 탐색해가는 식으로 구현하면 된다.
어렵지 않은 문제.
BOJ 14494: 다이나믹이 뭐예요?
BOJ 2668: 숫자고르기
Link : https://www.acmicpc.net/problem/2668
solution
사이클이 생기는 수열들의 집합을 찾아야 한다.
N의 상한이 충분히 작아서 사이클임을 알기 위해 DFS를 돌려줬고
사이클이라면 돌아오면서 ans[]에 표시하도록 했다.
BOJ 5373: 큐빙
Link : https://www.acmicpc.net/problem/5373
소스 코드
solution
여태까지 풀어본 구현 문제 중 끝판왕이다. 위에 있는 BOJ 16939: 2×2×2 큐브는 몸풀기인듯.
어디서 이 문제가 구현이 골치 아프다는 글을 한참 전에 읽고 겁나서 시도를 안해보다가
여기에 시뮬레이션 문제로 올라와 있어서 패기있게 도전하고 머리가 깨지는 경험을 했다.
이 문제는 qna에 반례가 제출 수에 비해 생각보다 많이 올라와있지 않다. (물론 도움되는 반례도 있었다! 👍)
왜 그런가 하니 큐브를 시뮬레이션 할 수 있는 사이트가 있었다.
반례가 도대체 뭘까 하며 찾아보다 이런 사이트가 있지 않을까 해서 먼저 찾았는데.. 사람 생각하는거 다 비슷한거 같다.
구현하는 아이디어 자체는 간단하다. 일단 면이 6가지가 존재한다. 그리고 돌리는 방향은 시계, 반시계 2가지다.
그럼 면을 하나 정하고 돌리려는 방향도 정했다면 그 면을 돌렸을 때 어느 부분이 달라지는지 생각해보자.
4개의 면에서 값이 변한다는걸 금방 알 수 있는데, 문제는 인덱스 값 자체에서 규칙성이 잘 안보인다.
(하나하나 업데이트하다 보면 대충 어떻게 처리하면 되겠네 싶은 규칙성은 감이 살짝 오긴 하지만
인덱스 값 즉, ‘숫자’만 보고 어떻게 처리하는게 편하겠거니 싶은 규칙성은 보이질 않았다.)
이 부분 때문에 함수 구현 대부분을 하드 코딩으로 처리했다. 소스 코드가 굉장히 긴 이유가 바로 이 부분이다. 😇
아무튼 구현을 하면 되는데, 주의할 점은 한 면을 잡고 돌렸을 때 해당 면의 값도 방향에 따라 변한다.
위에 시뮬레이션하는 사이트에서 테스트해보면 쉽게 알 수 있다. 이 부분때문에 시계/반시계 구현을 함수로 따로 만들어줬다.
다시는 풀고싶지 않은 문제다.
이 문제도 삼성 기출이라는데 실전에서 이걸 빠르게 풀고 통과한 사람은 거의 없을거 같다.
구현 문제는 알고리즘처럼 알지 못하면 손도 못대는 그런 유형이 아니기 때문에
누구나 덤벼들 수 있지만 난이도가 올라가면 일단 손도 대기 싫어지는거 같다. 풀기 싫다는걸 뭘 이렇게 쭝얼쭝얼 썼지?
그래도 이런 문제를 경험해보는게 후에 더 좋은 영향을 주기는 하는것 같다. 구현 실력도 그렇고 멘탈적인 측면에서도.
으아아 😵
BOJ 2307: 도로검문
Link : https://www.acmicpc.net/problem/2307
solution
아무 길을 막지 않은 상태에서 다익스트라를 돌려 최단 거리를 구한 후 기준으로 잡는다.
1~N까지의 최단 경로를 route[]에 담고 경로를 1개씩 막아서 다익스트라를 돌려본다.
만약 완전히 막아서 N으로 도달하지 못할 경우 -1을 출력하고
그렇지 않은 경우 (기준 - 최단 거리)의 최댓값을 구하면 된다.
BOJ 14863: 서울에서 경산까지
Link : https://www.acmicpc.net/problem/14863
solution
DP 문제.
도시 a에서 b로 가는 방법은 도보, 자전거 단 2개 뿐이다. 케이스도 2개뿐이므로 모든 경우를 돌려주면 된다.
BOJ 16918: 봄버맨
Link : https://www.acmicpc.net/problem/16918
solution
가로, 세로, 시간 범위가 크지 않으므로 구현에만 신경쓰면 된다.
폭탄이 터지는 시간이 0이 됐다고 곧바로 터뜨리면 옆에있는 터져야 하는 폭탄이 터지지 못하는 경우가 발생한다.
때문에 영향을 받는 좌표를 전체를 탐색하며 담아둔 후 마지막에 터뜨리도록 처리했다. 이부분만 유의하면 될 것 같다.
BOJ 14430: 자원 캐기
BOJ 2641: 다각형그리기
Link : https://www.acmicpc.net/problem/2641
solution
구현 문젠데 처음에 어떻게 풀어야 할지 감이 바로 오질 않았다.
여러 시행착오 끝에 (0,0) 기준으로 입력받은 방향대로 좌표를 이동하면서 담은 뒤
가장 왼쪽 아래(코드에서는 정렬했을 때 가장 앞에 오는 값)에 있는 좌표를 다시 기준 잡아
(0,0)으로 평행이동할 때 이동하는 만큼 모든 좌표도 똑같이 평행이동 시켜줬다.
그렇게 했을 때 표본 모양수열과 좌표가 모두 같다면 답을 갱신해주도록 했다.
BOJ 17396: 백도어
Link : https://www.acmicpc.net/problem/17396
solution
마지막을 제외한 분기점 중 상대방 시야에 보이는 곳은 경로로 추가하지 않으면 된다.
다익스트라로 풀어주면 된다. 오버플로우에 주의.
BOJ 16985: Maaaaaaaaaze
Link : https://www.acmicpc.net/problem/16985
solution
미로에서 탈출구를 찾는 BFS 문제를 풀어봤다면 이 문제도 역시 같은 방식으로 풀 수 있다. 다만 3차원이다.
방식은 달라지지 않지만 구현이 조금 까다롭다. 층을 임의로 설정할 수도 있고, 출발점 또한 4가지를 선택할 수 있다.
또한 각 면을 회전시킬 수 있다는 점도 까다롭게 하는 요소중 하나다.
각 면이 어디 층으로 들어가는지는 임의로 설정되기 때문에 순열을 만들어주는 next_permutation을 이용했고
각각 회전한 횟수 또한 0~4회이므로 이 부분은 5면에 대해 5중 for문을 돌려줬다.
이렇게 케이스를 모두 만들어줬다면 각각 BFS를 돌려 맨 마지막 면의 도착점까지 가는 최단 거리를 취하면 된다.
구현하는데 좀 답답했고, AC를 받았지만 통과한 시간이 너무 길어서 또 답답했다.
BOJ 17175: 피보나치는 지겨웡~
Link : https://www.acmicpc.net/problem/17175
solution
문제 설명에 주어진 코드대로 돌렸을 때 함수가 호출되는 횟수를 구해야 한다.
당연히 DP로 풀어야 하는데 본인이 호출되는 횟수까지 세므로 기존 피보나치에서 1을 더하도록 하자.
기저 사례도 다르니 주의.
BOJ 2637: 장난감조립
Link : https://www.acmicpc.net/problem/2637
solution
f(a, b) : a번 제품을 만드는데 필요한 재료 b의 갯수
처음에 입력받는 M개의 줄에서 기본 제품을 걸러낸 후 완제품에서 기본 제품의 갯수를 취해오는 방식을 택했다.
완제품을 이루는 재료들은 기본/중간 제품이 있는데 여기서 중간 제품은 또 기본 제품들로 이루어져 있으므로
DP로 풀어내야 효율적으로 풀어낼 수 있겠다.
BOJ 14431: 소수마을
Link : https://www.acmicpc.net/problem/14431
solution
마을을 2개 잡고 거리가 소수면 양방향으로 간선을 담아준 후 다익스트라를 돌리면 된다.
소수는 에라토스테네스의 체로 처리하자.
BOJ 16986: 인싸들의 가위바위보
Link : https://www.acmicpc.net/problem/16986
solution
구현 문제다. 문제 설명을 좀 꼼꼼히 읽어야 할 필요가 있다.
처음에 설명을 대충 읽고 사진만 보고 아! 이긴 사람이 왼쪽으로 오는구나! 했는데 TC부터 틀렸다.
설명에 있는 규칙 2을 잘 읽어보면, 비겼을 때 경기 진행 순서 뒤인 사람이 이긴 것으로 간주한다고 언급 돼있다.
따라서 지우, 경희, 민호를 1, 2, 3이라 부르면 지우 vs (경희 or 민호)일 때 A[i][j]가 0 또는 1이면 무조건 지우가 지게 된다.
(즉, 이전 승패 정보와는 관련없이 값의 크기(순서)에 따라 달라진다는 점이다)
또한 지우가 k번 이겨야하긴 하지만 다른 친구들이 k번을 먼저 이기면 곤란하다. 때문에 이 경우도 커팅해줘야 한다.
고려해야할 부분이 꽤 많아서 구현하는데 힘들었다. 재귀로 짠 덕분에 코드는 생각보다 간결해졌지만 많이 고생했다.
BOJ 5721: 사탕 줍기 대회
Link : https://www.acmicpc.net/problem/5721
solution
DP 문제.
조금 특이한 점은 세로, 가로의 상한이 별도로 주어지지 않았다는 점이다.
이 부분때문에 처음에 벡터 resize를 통해서 풀어보려 했는데 이게 메모리 할당이랑 직접적으로 연관된게 아닌건지
아니면 내가 모르는 부분이 또 있는건진 모르겠지만 런타임 에러가 떠서 캐시를 2차원 배열이 아닌 1차원 배열로 설정했다.
가령, m=3, n=5이고 특정 좌표가 (1, 4)라면 $1\times 5+4 = 9$로 나타낼 수 있다. (0-based index)
행과 열을 직접적으로 써야할 경우 위 값을 n의 몫, 나머지로 다시 분해해서 사용하면 된다.
- 원소 하나를 선택했다면 같은 행에서는 이웃한 원소를 선택하지 못한다. 따라서 2칸 더 오른쪽으로 이동해야 한다. (+a[x][y])
- 선택하지 않는다면 1칸 오른쪽으로 이동할 수 있다. 대신 답에 갱신하진 않는다.
- 다음 칸(y+1) 또는 다다음칸(y+2)이 n보다 크거나 같을 경우, 다음 행의 첫 번째 원소로 넘어가도록 해주자.
BOJ 16987: 계란으로 계란치기
Link : https://www.acmicpc.net/problem/16987
solution
설명을 슥 읽고 뚝딱뚝딱 짠 후에 TC를 돌려봤는데 답이 쉽게 나오질 않았다.
문제를 잘못 읽었나 몇 번을 검토해보다 잘 모르겠어서 나같은 사람이 있나 검색을 해봤는데
나같은 사람은 거의 없는 것 같고(..) 다만 설명에 대해서 쉽게 풀어쓴 글이 있어서 참고하고 AC를 받을 수 있었다.
설명에 있는 계란을 치는 과정에서 2번이 헷갈렸다.
이게 기준 계란으로 다른 계란을 치긴 치는데 적어도 한 쪽이 깨질 때까지 치는건지(TC 9번이 반례)
한 번만 치고 기준 계란으로 남은 깨지지 않은 다른 계란들을 또 치러 가는건지(TC에서 한 두개 정도 틀림)
위 2가지에서 계속 삐걱삐걱댔는데 다른 분의 글을 읽어보니 그냥 한 번 치고 기준 계란을 다음으로 바꾸는 거였다. 😇
그냥 이렇게 짜주면 크게 어려운건 없다. N이 심히 적으니 브루트 포스로 해결할 수 있겠다.
BOJ 2655: 가장높은탑쌓기
Link : https://www.acmicpc.net/problem/2655
solution
DP 문제.
f(i) : 현재 맨 위에 있는 벽돌이 i번일 때 만들 수 있는 최대 높이
문제에 써진 기준에 따라 벽돌을 쌓고 재귀로 돌아가면서 답이 갱신(ret < f(i) + wall[i].h)될 때마다 from[i] 또한 갱신해주자.
from[i]는 i번 벽돌 위에 쌓을 벽돌의 번호를 가리킨다. 이 from[i] 덕분에 어떤 벽돌이 쌓였는지 역추적할 수 있다.
BOJ 12101: 1, 2, 3 더하기 2
BOJ 17610: 양팔저울
Link : https://www.acmicpc.net/problem/17610
solution
브루트 포스로 풀 수 있다.
매번 호출될 때마다 이용하지 않은 인덱스를 통해 현재 값에서 더하거나 빼는 연산을 해주려 했는데
이 방식으로는 TLE를 피할 수 없었다. (이미 나온 값을 visited에 추가하는건 WA를 받는다. 반례는 [1, 2, 3])
어차피 특정 인덱스를 사용할 차례가 왔을 때 사용하거나 사용하지 않거나 딱 2가지이기 때문에
사용하는 경우는 더하거나 빼는 연산을, 사용하지 않는 경우는 현재 값에 영향을 주지 않도록 처리해주고
다음 인덱스로 넘어가는 방식으로 짜주면 시간 문제없이 충분히 통과할 수 있다.
즉, 함수가 호출될 때마다 [0, n)을 모두 돌면서 처리해줄 필요가 없다는 말.
카테고리에 DP로도 분류가 돼있던데 아마 비슷한 방식으로 돌아가되 메모이제이션을 해주는 것 같다.
BOJ 16988: Baaaaaaaaaduk2 (Easy)
Link : https://www.acmicpc.net/problem/16988
solution
DFS로 상대의 돌의 집합을 먼저 묶어준 뒤(makeArea()) 2개의 빈 칸을 찾아가면서 돌을 놓았다고 가정한 후
각 집합이 둘러쌓였을 경우(blank=0) 답을 갱신하도록 해줬다.
2개를 놓을 수 있는 모든 경우의 수를 뒤져봤기 때문에 결론적으로는 브루트 포스로 풀었다.
아이디어도 금방 짜고 구현도 틀을 잡기까지는 얼마 안걸렸지만 몇몇 TC에 걸려서 제출하기까지 시간이 좀 걸렸다.
걸렸던 TC가 없었다면 꽤나 애먹었을 것 같다.
BOJ 12849: 본대 산책
Link : https://www.acmicpc.net/problem/12849
solution
정보대를 1번이라 했을 때, 건물 수가 적으므로 인접 행렬(adj[][])로 나타내준 뒤
D분 뒤에 1번에 도달하는 경우를 DP로 세주면 된다.
댓글남기기