복습 4

설탕배달부터

까먹은 문제

1. 설탕배달 - Math

   n,m으로 k를 의 최소의 개수를 맞추는 방식

2. 2XN 타일링 - DP

   dp는 일단 간단한 점화식부터 생각해보자

3. 토마토 2 - BFS

   3차원 배열 이용하는 법

   int y = Integer.parseInt(n[0]); // 열 -> 가로로 y개라는 뜻
   		int x = Integer.parseInt(n[1]); // 행 -> 세로로 x개라는 뜻
   		int z = Integer.parseInt(n[2]); // 높이
      		
   		int maze[][][] = new int[z][x][y]; // 맵에 데이터 넣기
      		
   		Queue<Poos> tomato = new LinkedList<>();
      		
   		//행개수만큼 넣고 -> 열 -> 높이
   		for(int i=0;i<z;i++) {
   			for(int j=0;j<x; j++) {
   				//한줄씩 받아온거 행에 넣기 ->행 개수만큼
   				String a[] = sc.nextLine().split(" ");
   				for(int k=0;k<y; k++) {
   					maze[i][j][k] =Integer.parseInt(a[k]);
      					
   					if(maze[i][j][k] == 1)
   						tomato.add(new Poos(j,k,i,0));
   				}//for - k
   			}//for - j
   		}//for - i
   

4. 쉬운 계단 수 - DP

   이차원 배열 이용한 문제

완벽 이해

1. 성실한 개미 - Maze

   dfs도 bfs도 아닌 오른쪽아니면 밑으로만 가는 문제!

2. ATM - Greedy

   answer = answer + i; k = k+answer;

3. 동전 0 - Greedy

   동전 종류에 따라, 최소의 동전개수 구하기

4. 회의실 배정 - Greedy

   Arrays.sort(arr, new Comparator<int[]>(){
      
   a[0]a[1]    
   b[0]b[1]
          
   @Override
   	compare(int a[], int b[]){
      
   	if(a[0]==b[0])
   		return a[0] - b[0]; // [0][1] -> 0번째에 맞춰 오름차순!
        else
            return a[1] - b[1]; // [0][1] -> 1번째에 맞춰 오름차순 정렬
      
   }})
   

5. 연결요소의 개수 - DFS

   네트워크와 같은 문제, CHECK[] 까지먹지 말자

6. 정수삼각형 - DP

7. 거스름 돈 - Greedy

   동전 종류에 따라, 최소의 동전개수 구하기

8. 초콜릿 자르기 - Math

9. 영역 구하기 - DFS

   두 좌표가 주어졌을 때 좌표를 표시하는 방법

   (2,5) (3,7)의 영역을 구하기 위해 사용한 식
      
   	for(int i=0;i<k;i++){
               int lx = sc.nextInt();
               int ly = sc.nextInt();
               int rx = sc.nextInt();
               int ry = sc.nextInt();
                  
               for(int y = ly; y<ry; y++){
                   for(int x= lx; x<rx; x++){
                       arr[y][x] = 1;
                   }
               }//in for
           }//out for
   

10. 연구소 - DFS

    Combination과 Dfs의 콜라보

11. 안전 영역 - DFS

12. 포도주 시식 - DP

13. 로프 - Greedy

14. 연속합 - Math

15. 그룹단어체커 - 문자열

16. 크로아티아 알파벳 - 문자열

    if(a.contains(words[i]))
    				a = a.replaceAll(words[i], "*");
    

17. 나이트의 이동 - BFS

18. 이친수 - DP

19. 30 - Greedy

    • 30의 배수가 되는 가장 큰 수
    1. 각 자리수의 합이 3의 배수이다.
    2. 0의 개수가 1개 이상이다.

20. 대회 or 인턴 - Greedy

21. 방번호 -Math

    arr[6] = Math.round(arr[6]/2.0f); // 반올림 하는 함수