알고리즘매일매일

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH

자석들이 회전할 방향을 미리 저장해놓고 풀면 쉽게 풀 수 있는 문제이다.

회전시킬 자석의 왼편과 오른편 자석들을 모두 회전할지 안 할지 검사한다.

회전을 하게 된다면 옆에 있는 자석의 반대방향으로 회전한다.

오른편의 자석들을 검사할 때는 순차적으로 왼쪽 자석의 2번 날과 오른쪽 자석의 6번 날을 비교하여

다를 경우에 오른쪽 자석의 회전 방향을 왼쪽 자석의 회전방향의 반대방향으로 저장한다.

마찬가지로 왼편 자석들을 검사할떄도 왼쪽 자석의 2번 날과 오른쪽 자석의 6번 날을 비교하여

회전 방향을 저장한다. 

날의 자성이 같아서 회전하지 않을 경우에는 그 앞의 자석들도 회전하지 않으므로 검사를 중단한다.

회전 방향을 모두 저장해줬다면 이제 모든 자석들을 회전시킨다.

1이면 시계방향 -1이면 반시계방향으로 회전시켜준다.

0인 경우(회전하지 않는 경우)도 있으므로 조건 처리를 정확히 해주어야 한다.

회전까지 모두 마쳤다면 점수를 계산해준다.

문제에서의 화살표 방향은 각 자석의 0번째 날이므로 자석들의 0번째 날이 S극인지(1 인지) 확인하여 계산해주면 된다.

점수는 각각 1, 2, 4, 8로 2의 제곱수로 더해지므로 << 연산으로 쉽게 더해줄 수 있다.

( 1<< 0 은 1이므로 1점 /  1<<1 은 10(2진수)으로 2점 / 1<<2는 100(2진수)으로 4점 / 1<< 3 은 1000(2진수)으로 8점)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

출발할 수 있는 모든 칸에서부터 출발하여  대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아온다.

n-1행, n-2행, 0열, n-1열인 곳에서는 사각형을 만들 수 없으므로 출발할 수 없다.

각 칸에서 출발하면 오른쪽아래(1,1), 왼쪽 아래(1,-1), 왼쪽 위(-1,-1), 오른쪽 위(-1,1)의 순서로 사각형을 그리도록 했다.

시작점인 경우에만 현재 방향을 유지해서 진행하고 그렇지 않은 경우에는

방향을 꺾어서 이동하는 경우와 현재 방향을 유지한채로 이동하는 경우를 모두 탐색했다.

같은 종류의 디저트를 먹으면 안되므로 디저트의 종류를 인덱스로 방문 체크를 해준다.

이동할 곳의 디저트를 아직 먹지 방문하지 않았다면 방문 체크를 해주고 다음 칸으로 이동한다.

이동할 때마다 디저트의 개수를 세주기 위해서  cnt 값을 +1 해서 넘겨준다.

이동하다가 이미 방문한 디저트 카페 이지만 그곳이 시작점인 경우에는 출발한 카페로 돌아온 경우이므로

그때까지의 방문한 디저트의 수를 비교해준다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

java로 두 번이나 풀어봤던 문제였는데 16진수로 변환하는 부분이 조금 달라서 푸는데 꽤 어려웠다...

먼저 한칸씩 회전시켜서 만들 수 있는 모든 숫자를 만들어야 하므로 N/4번만큼 돌려준다.

N/4번만큼 돌리면 처음 상태로 돌아오기 때문이다.

숫자를 구할 때는 먼저 문자들을 숫자로 변환해준다.

문자 0~9는 '0'을 빼줘서 숫자 0~9로 만들어주고

문자 A~F는 'A'를 빼주고(0이 됨) +10을 해주면 16진수 처럼만들어 줄 수 있다.

(ex. 'A' - 'A' + 10 = 10

      'B' - 'A' + 10 = 11)

모든 문자를 숫자로 만들어 줬으면 이제 각 변에 저장될 숫자를 만들어 준다.

상자는 네 번 이므로 각 변에는 n/4만큼의 숫자가 들어간다.

n/4개의 숫자를 하나의 숫자(16진수)로  만들어주기 위해서 앞자리 수를 16만큼 계속 곱해준다.

한 변의 숫자가 만들어졌으면 벡터에 추가하고 다음 변의 숫자를 만들어준다.

만들 수 있는 모든 숫자를 벡터에 넣어줬다면

벡터를 정렬하고 중복을 제거해준다.

k 번째로 큰 수를 구해야 하는데 오름차순으로 정렬되므로 

벡터의 size - k를 해주면 바로 k번째 큰 수를 구할 수 있다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

이 문제에서 k의 범위는 현재 좌표가 (x, y)라고 했을 때, 

k = |nx-x| + |ny-y|

를 이용해서 k의 범위를 만족하는 (nx, ny)를 구할 수 있다.

위의 식을 이용하여 모든 칸에서부터 모든 k의 범위 안에서 집의 수를 구한다.

문제에서 나오는 식을 이용하여 이익을 계산한 후에 손해가 아니라면(이익이 0 이상이라면) 최댓값과 비교한다.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

Fail을 엄청 많이 한 문제였다ㅠㅠ 심지어 이번에 다시 풀어본 것임에도 불구하고 4번 만에 Pass 했다...

보호 필름 문제는 dfs를 사용하여 각 막에 약물 A를 투여하는 경우, B를 투여하는 경우, 약물을 투여하지 않는 경우를 모두 구해줬다.

이 문제에서주의할 점은 합격 기준인 K가 1인 경우다.

K가 1인 경우 무조건 합격이므로 검사를 해줄 필요 없이 바로 0을 출력해주어야 한다.

완전 탐색

먼저 K==1 인 경우에는 0을 출력해주도록 처리하고 바로 다음 테스트 케이스로 넘어간다.

K가 1보다 큰 경우에는 각 막에 약품을 투여하여 변경된 상태를 새로 적용해주기 위해서 매번 새로운 배열을 만들어주었다.(메모리를 많이 써서 다른 방법을 쓰는 게 좋을 것 같다...)

현재 투여한 약물의 수가 이미 기준을 통과한 최솟값을 넘어간다면 더 검사할 필요가 없으므로 return 하도록 백트래킹을 해준다.

매번 dfs에서는 합격하는지 검사해주고 기준을 통과했다면 min값을 바꾸고 return 한다.(통과한 시점에서 더 많은 약물을 투여할 필요가 없기 때문)

모든 막에 대한 약물 투여 여부를 결정해준 경우에도 return.

합격 기준 검사

합격 기준을 검사하는 부분에서는 모든 열에 대해서 합격 기준을 통과하는지 검사해준다.

하나의 열이라도 합격기준을 통과하지 못하면 합격하지 못한다.

각 열에 대해서는 연속하는 K개의 셀이 같은 값인지 검사해주고 한 번이라도 그러한 경우가 있다면 다음 열의 검사로 넘어간다.

import java.io.*;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int D,W,K, min;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            int[][] film = new int[D][W];
            for(int i=0; i<D; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<W; j++) {
                    film[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
 			
            //합격 기준이 1인 경우 바로 0을 출력하고 다음 테스트 케이스로 넘어간다.
            if(K == 1) {
                System.out.println("#"+tc+" "+0);
                continue;
            }
             
             
            min = D+1; //약물을 투여하는 최대 개수는 D개이므로 적당히 D+1정도로 설정해주었다.
            dfs(film,0,0);
            System.out.println("#"+tc+" "+min);
        }
    }
     
    static void dfs(int[][] film, int index, int count) {
    	//현재 약품 투여 횟수가 이미 최솟값을 넘은 경우 더 검사할 필요가 없으므로 return
        if(count >= min) return; 
        
        
        //합격 기준을 통과한 경우 최솟값을 count값(현재 약품 투여 횟수)으로 변경하고 return
        if(test(film)) {
            min = count;
            return;
        }
        
        
        //막의 범위를 넘어가는 경우 return
        if(index == D) return;
         
         
        //새로 넘겨줄 배열 생성
        int[][] arr = new int[D][W];
        for(int i=0; i<D; i++) {
            for(int j=0; j<W; j++) {
                arr[i][j] = film[i][j];
            }
        }
         
         
        //index행에 약품을 투여하지 않는 경우
        dfs(arr,index+1,count);
         
         
        //index행에 A약품을 투여하는 경우
        for(int j=0; j<W; j++) {
            arr[index][j] = 0;
        }
        dfs(arr,index+1, count+1);
        
        
        //index행에 B약품을 투여하는 경우
        for(int j=0; j<W; j++) {
            arr[index][j] = 1;
        }
        dfs(arr,index+1, count+1);
         
    }
     
    static boolean test(int[][] film) {
        boolean flag = false;
 
 		//모든 열을 검사 
        for(int j=0; j<W; j++) {
        
        	//각 열의 셀을 모두 검사 
            for(int i=0; i<=D-K; i++) {
                flag = true;
                
                //각 열에서 K개만큼의 연속적인 셀을 검사 
                for(int l=i+1; l<i+K; l++) {
                    if(film[i][j] != film[l][j]) {
                        flag = false; //K개만큼 연속적으로 같지 않으면 break 하고 밑의 셀부터 다시 검사 
                        break;
                    }
                }
                 
                //K개 연속적으로 같은 셀이 있으면 한 번이라도 있으면 이번 열은 바로 통과하고 다음 열로 넘어간다.
                if(flag) break;                 
            }
             
            //이번 검사한 열이 검사를 통과하지 못하므로 아예 테스트 통과 불가능 
            if(!flag) break;
        }
         
        if(!flag)
            return false;
        else
            return true;
    }
     
}

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH

풀이

1. 먼저 각 자석의 자성 정보를 배열에 저장한다.
2. 입력받은 K번만큼 실행
   1. 회전시킬 자석 번호와 방향을 입력받는다.
   2. 처음 상태에 따라서 회전할지 안 할지가 결정되므로 미리 회전방향을 배열에 저장해놓는다.
   3. 회전시킬 자석의 오른쪽과 왼쪽의 자석들을을 각각 순차적으로 검사한다.
   4. 앞의 자석의 2번째 날과 뒤의 자석의 6번째 날을 비교한다.
   5. 같으면 그쪽 방향의 자석들은 회전하지 않을 것이므로 break
   6. 다르면 현재 회전하는 자석의 반대 방향으로 회전 방향을 저장한다.
   7. 각 자석을 위에서 저장한 회전 정보를 이용하여 회전시켜준다.
      1. 0인 경우는 회전하지 않는 자석
      2. 1인 경우는 시계방향 회전
      3. -1인 경우는 반시계 방향 회전
3. K번만큼의 회전이 끝난 후에 총점을 계산해준다.
4. 1,2,4,8 순으로 점수가 늘어나므로 left shift (<<) 연산을 사용해서 sum 변수에 더해줬다.

import java.io.*;
import java.util.StringTokenizer;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int tc=1; tc<=T; tc++) {
			int K = Integer.parseInt(br.readLine());
			int[][] info = new int[4][8];
			for(int i=0; i<4; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<8; j++) {
					info[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
            //명령을 K번 실행
			for(int i=0; i<K; i++) {
				st = new StringTokenizer(br.readLine());
				int num = Integer.parseInt(st.nextToken())-1;
				int dir = Integer.parseInt(st.nextToken());
                
				int[] rotation = new int[4]; //회전할 방향을 저장
				rotation[num] = dir;
				
                
                //오른쪽 자석들을 검사
				for(int j=num+1; j<4; j++) {
					if(info[j-1][2] == info[j][6]) //자성이 같으면 회전하지 않는다.
						break;
					else
						rotation[j] = -rotation[j-1];
				}
				
                
                //왼쪽 자석들을 검사
				for(int j=num-1; j>=0; j--) {
					if(info[j][2] == info[j+1][6]) //자성이 같으면 회전하지 않는다.
						break;
					else
						rotation[j] = -rotation[j+1];
				}
				
				
                //각 자석을 회전시킨다.
				for(int j=0; j<4; j++) {
					if(rotation[j] == 0) continue; //회전하지 않는 경우
					else if(rotation[j] == 1) { // 시계방향 회전
						int tmp = info[j][7];
						for(int k=7; k>0; k--) {
							info[j][k] = info[j][k-1];
						}
						info[j][0] = tmp;
					} else if(rotation[j] == -1) { // 반시계방향 회전
						int tmp = info[j][0];
						for(int k=0; k<7; k++) {
							info[j][k] = info[j][k+1];
						}
						info[j][7] = tmp;
					}
				}
				
			}
			
            
            //모든 실행이 끝난 후 총합을 계산
			int sum = 0;
			for(int i=0; i<4; i++) {
				if(info[i][0] == 1) {
					sum += 1<<i;
				}
			}
			
			System.out.println("#"+tc+" "+sum);
		}	
	}

}