백준

[백준, Java] 9465번 : 스티커

🔗 문제 링크 https://www.acmicpc.net/problem/9465 😮 문제 해결 방법 매 열마다 1행 혹은 2행의 스티커를 뜯었을 때의 최대 점수를 구해주면 되기 때문에 2차원 배열로 선언해준다. 최대 점수는 n열까지 모두 뜯었을 때 1행 n열 혹은 2행 n열의 점수 중 큰 점수가 가장 최대로 구할 수 있는 점수이다. 현재 열이 3열이라고 가정하고 스티커를 뜯는 경우를 판단해보자. 3열의 스티커를 뜯는 경우는 1행 3열, 2행 3열의 스티커를 뜯는 경우 2가지이다. 1행 3열의 스티커를 뜯는 경우 → row : 0 col : 2 인접한 변을 가진 스티커는 뜯을 수 없기 때문에 **이전 열 대각선(현재 행과 반대되는 행)**에 위치한 최대 점수 값과 현재 스티커 점수를 더해준다. → dp[p..

[백준, Java] 1052번 : 물병

🔗 문제 링크 https://www.acmicpc.net/problem/1052 😮 문제 해결 방법 문제에서 같은 양이 들어있는 물병끼리 하나로 합칠 수 있고 처음에는 모든 물병에는 물이 1L가 들어있다고 제시되어 있다. 처음부터 두 개의 물병을 한 개의 병으로 합쳐가면, 2L → 4L → 8L 이런식으로 증가할 수 밖에 없다. 이는 물병이 2의 제곱 값이 되어야 병이 하나로 합쳐지는 것을 알 수 있다. N개의 물병을 K개의 물병으로 합치는 경우 최소 개수의 물병을 사기 위해선 남은 물병(N) 보다 작으면서 가장 큰 2의 제곱 값을 매번 구해 빼주는 작업을 K-1번 해주고, 그래도 물병이 남아있다면 마지막(K번째)에는 남은 물병으로 한 병을 만들어야 하므로 남은 물병보다 크면서 가장 작은 2의 제곱값을 ..

[백준, Java] 9663번 : N-Queen

🔗 문제 링크 https://www.acmicpc.net/problem/9663 😮 문제 해결 방법 첫 번째 행부터 차례로 모든 배치에 퀸을 놓아보는 방식의 완전탐색 문제이다. 퀸을 배치하기 전에 이전 행에 놓인 퀸 들이 움직일 수 없는 위치에 놓아야 하기 때문에 행 마다 퀸을 배치하면서 이전 행의 퀸의 배치와 겹치지 않는지 판단하는 로직을 추가한다. 이전 행의 퀸들과 겹칠 수 있는 경우는 2가지가 있다. 이전 행들에 놓인 퀸의 열과 현재 놓을 퀸의 열이 동일한 경우 이전 행들에 놓인 퀸과 현재 놓을 퀸이 대각선에 존재하는 경우 동일한 행에 퀸이 놓이는 경우도 고려해야하지만, 재귀를 이용해 한 행 (depth)마다 퀸을 배치할 것이기 때문에 동일한 행에 두 개이상의 퀸이 놓이는 경우는 발생하지 않는다. ..

[백준, Java] 18352번 : 특정 거리의 도시 찾기

🔗 문제 링크 https://www.acmicpc.net/problem/18352 😮 문제 해결 방법 문제의 조건에서 최대 300,000개의 도시가 입력으로 주어질 수 있다고 명시했기 때문에, 인접행렬 방식이 아닌 인접 리스트 방식으로 해결해야한다. 시작 도시부터 도달할 수 있는 모든 도시에 대해 최단거리를 구하는 알고리즘은 “다익스트라"를 사용할 수 있다. 물론, 해당 문제에서도 다익스트라 알고리즘을 사용할 수 있지만, 각 도시간 거리가 1로 고정이 되어있기 때문에 BFS를 이용해서도 문제를 해결할 수 있다. 출발 도시를 시작으로 BFS를 구현한다. 연결된 도시 중 방문하지 않고, 현재 도시에서 거리에 +1 한 값보다 연결된 도시 거리가 멀다면 최단 거리로 갱신한다. 시작 도시로 부터 도달할 수 있는 ..

[백준, Java] 1062번 : 가르침

🔗 문제 링크 https://www.acmicpc.net/problem/1062 😮 문제 해결 방법 문제에서 남극 단어의 시작과 끝은 anta, tica로 끝난다고 했기 때문에 a,n,t,i,c는 반드시 배워야 하는 글자이다. a,n,t,i,c를 포함해 남은 알파벳 중 k개를 조합한다. 조합한 알파벳을 남극 단어마다 해당 알파벳을 모두 포함하는지 판단하면서 배울 수 있는 단어를 체크한 후 현재 까지 최대로 배울 수 있는 단어 개수와 현재 배울 수 있는 단어 개수를 비교해서 갱신한다. a,n,t,i,c는 반드시 배워야 하는 글자이므로 K가 5보다 작다면 남극 단어를 배울 수 없기 때문에 0을 리턴한다. K가 5보다 크다면 이미 5개를 배웠기 때문에 a,n,t,i,c를 제외한 (K - 5)개의 글자를 백트래..