완전 탐색
문제 설명을 짧게 하면
5 5
W W W W W
W W W W W
W B W W W
W W W W W
W W W W B이런 입력 값이 주어지면
(행, 열) 기준으로 다음 2가지 방법이 가능합니다.
두 방법 모두 밟게되는 위치에 적혀있는 색이 'W', 'B', 'W', 'B' 순으로 조건을 만족하게 됩니다.
(1, 1) → (3, 2) → (4, 3) → (5, 5)
(1, 1) → (3, 2) → (4, 4) → ( 5, 5)1행 1열부터 시작해서 계속 다른 색을 밟으면서 움직일 수 있는 케이스를 구하는 문제이다.
처음에는 입력 값만 보고 단순화해서 B 시작할 떄부터 완전탐색으로 모든 케이스를 찾으면 되겠군! 이렇게 접근했다.
for(int i=0; i<r; i++){
for(int j=0; j<c; j++){
if(arr[i][j] == 'B' && i != r-1 && j != c-1){
for(int k=i+1; k<r-1; k++){
for(int l=j+1; l<c-1; l++){
if(arr[k][l] == 'W')
count++;
if(arr[k+1][j+1] == 'B')
break;
}
}
}
}
}근데 너무 단순화 시켰는지, 복잡하게 B가 등장하는 케이스에서는 너무 많이 카운트 되버렸다.
그래서 해설을 살짝 참고하니까
for(int i = 1; i < n; i++)
for(int j = 1; j < m; j++)
for(int k = i + 1; k < n - 1; k++)
for(int l = j + 1; l < m - 1; l++)
if(grid[0][0] != grid[i][j] &&
grid[i][j] != grid[k][l] &&
grid[k][l] != grid[n - 1][m - 1])
cnt++;
B, W를 이분법적으로 일반화해서 되게 깔끔한 조건으로 표현했다.
어떨 때는 일반화하느라 풀이가 너무 복잡해져서 못 푼 적도 있었는데, 이렇게 이분법적인 상황에서는 좋은 접근법인 것 같다.
어려운 문제는 아닌데, 삽질을 많이 했다..
이 문제에서 포인트는
1. 문제에서 주어진 값 조작하지 않기
2. 큰 단위로 나눠서 로그 찍어서 값 확인하기
풀이는 아래와 같다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
int max = -1;
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
for(int k=j+1; k<n; k++){
int[] num = new int[5];
int index = 4;
int sum = arr[i] + arr[j] + arr[k];
int a = arr[i];
int b = arr[j];
int c = arr[k];
while(index >= 0){
num[index] += a % 10;
a /= 10;
num[index] += b % 10;
b /= 10;
num[index] += c % 10;
c /= 10;
if(num[index] > 9) break;
index--;
}
//System.out.println(a + " " + b + " " + c + " " + index);
if(index == -1 && num[++index] < 10)
max = Math.max(sum, max);
}
}
}
System.out.print(max);
}
}마라톤 중간에 택시타기 2
이 문제는 처음에 못 풀었는데, 이 문제의 해결 과정을 되짚어보면서 문제들을 접근할 때 어떤 방식으로 접근해야 하는지 생각해보는 기회가 되었다.
- 풀이의 방향을 간단하게 적어보기
- 상수(일정한 값)와 변수 분석하기
- 변수들을 상수(일정한 값)로 만들 방법 생각하기
원 모양으로 되어있는 방
문제는 어렵지 않지만 풀이가 흥미롭다.
반시계 방향으로 움직이는 것을 코드로 표현해야 한다.
나는 잘 감이 안 와서 예시를 나열하면서 규칙을 찾아서 풀었다.
코드의 의미를 분석하면 방들의 거리를 일정하게 만들고 방을 회전시켜서 해결하는 방식이다.
for(int i=0; i<n; i++){
int dist = 0;
int index = 0;
for(int j=0; j<n; j++){
dist += Math.abs(room[(i + index) % n] * j);
index++;
}
min = Math.min(min, dist);
}해설의 경우 방을 고정시키고 거리에 초점을 맞춰서 해결했다.
중심이 되는 방을 기준으로 거리에 부호를 붙여서 반시계는 +, 시계방향은 -라고 생각하고 +n을 더해줘서 보정해준다고 생각해도 된다.
for(int i = 0; i < n; i++) {
int sumDist = 0;
for(int j = 0; j < n; j++) {
int dist = (j - i + n) % n;
sumDist += dist * a[j];
}
// 가능한 거리의 합 중 최솟값을 구해줍니다.
ans = Math.min(ans, sumDist);
}완전 탐색 + DFS
완전 탐색이랑 DFS가 결합된 문제이다.
사실 오랜만에 DFS 문제를 푸는 거라서 풀이가 가물가물해서 못 풀긴 했는데, 고민의 핵심은 이거였다.
'방향이랑 깊이 탐색이 다른데 같은 반복문으로 묶는 게 맞나?'
해설을 참고하니 방향은 for문으로, 깊이 탐색은 while문으로 따로 분리해서 해결하는 것이었다.
DFS의 정석같은 문제라서 여러 번 풀어봐야 할 것 같다.
풀이는 아래와 같다.
for(int i = 0; i < 19; i++) {
for(int j = 0; j < 19; j++) {
if(arr[i][j] == 0) continue;
for(int k = 0; k < DIR_NUM; k++) { // 모든 방향 탐색
int curt = 1;
int curx = i;
int cury = j; // 현재 위치랑 탐색할 위치 분리
while(true) {
int nx = curx + dx[k];
int ny = cury + dy[k]; // 탐색할 위치 계산
if(inRange(nx, ny) == false)
break;
if(arr[nx][ny] != arr[i][j])
break;
// 계산된 탐색할 위치 검증
curt++;
curx = nx;
cury = ny;
// 해당 위치로 이동
}
if(curt == 5) {
System.out.println(arr[i][j]);
System.out.print((i + 2 * dx[k] + 1) + " " + (j + 2 * dy[k] + 1));
System.exit(0);
}
}
}
}