이것저것 개발 블로그

https://www.acmicpc.net/problem/1003

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main_BJ_1003_피보나치함수 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc=1; tc<=t; tc++){
            int n = Integer.parseInt(br.readLine());
            int[][] dp = new int[n+1][2];

            dp[0][0] = 1;
            dp[0][1] = 0;

            if(n>=1) {
                dp[1][0] = 0;
                dp[1][1] = 1;
            }

            for(int i=2; i<=n; i++){
                dp[i][0] = dp[i-1][0] + dp[i-2][0];
                dp[i][1] = dp[i-1][1] + dp[i-2][1];
            }

            System.out.println(dp[n][0] + " " + dp[n][1]);
        }//for
    }//main
}

피보나치 문제에 대해 간단히 생각해볼 수 있는 문제였다.

단순히 dp 만들어서 해야지~~ 하다가 0과 1 또한 규칙성있게 계속 더해진다는 것을 알게되어서 신기했당.

예시)

https://www.acmicpc.net/problem/11726

풀이)

import java.util.Scanner;

public class Main_BJ_11726_2xn타일링 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}

나는 그냥 직접 그리며 찾아보면서 피보나치 수열인지 알았다.

또한, 문제 보자마자 dp인줄 알았다,,,ㅎㅎ

그런데, 논리적으로 찾아놓은 글이 있어서,,,ㅎㅎ 참고해보라고 올려놓는다!

https://kosaf04pyh.tistory.com/222

https://www.acmicpc.net/problem/1107

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_1107_리모컨 {
    static boolean[] broken = new boolean[10];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        if(m>0) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = 0; i < m; i++) {
                //고장난 버튼 체크
                broken[Integer.parseInt(st.nextToken())] = true;
            }
        }

        // case 1. 원하는 채널까지 +,-버튼만으로 이동
        // 초기 채널 = 100. => 초기값 설정
        int ans = Math.abs(n - 100);

        // case 2. n과 근접한 수에서  +,-으로 채널 이동
        // 완탐. 0부터 999999까지 모든 채널을 돌며 가장 적은 횟수로 이동할 수 있는 채널 찾기
        for(int i=0; i<1000000; i++){
            int num = i;
            // isPossible: 0이면 불가능, 1이면 가능
            int len = isPossible(num);
            if(len > 0){
                // adj: 숫자 버튼으로 n에 최대한 인접한 수에서 +와 -를 몇 번 눌러야 하는지 구하는 수
                int adj = Math.abs(num - n);
                if(ans > len+adj)
                    ans = len + adj;
            }
        }
        System.out.println(ans);
    }//main
    private static int isPossible(int num){
        if(num == 0){ // 0일때 예외처리
            if(broken[0])
                return 0;
            else
                return 1;
        }

        // num의 자리수 체크
        int len = 0;
        while(num > 0){
            if(broken[num%10]) // 자리수 체크하다 불가능할 경우
                return 0;
            len++;
            num /= 10;
        }
        return len;
    }//isPossible
}

아,,, 문제 풀면서 조금 어려웠다.

완탐이라고 생각도 잘 안들었고,,,ㅠㅠ

두 가지 케이스로 나누면 된다.

1. +,-버튼으로 모두 이동할 경우(버튼이 모두 고장났을 때로 생각하면 좋음)

2. 버튼에서 가장 인접한 번호에서 +,-버튼으로 이동할 경우

나머지는 주석에 달아놓았으니 참고하길!

https://www.acmicpc.net/problem/1874

풀이)

import java.util.Scanner;
import java.util.Stack;

public class Main_BJ_1874_스택수열 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = sc.nextInt();
        int index = 1;
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i<n; i++){
            int num = sc.nextInt();
            while(stack.isEmpty() || stack.peek() < num) {
                stack.push(index++);
                sb.append("+\n");
            }
            if(stack.peek() == num){
                stack.pop();
                sb.append("-\n");
            }
            else{
                System.out.println("NO");
                System.exit(0);
            }

        }//for
        System.out.println(sb);
    }//main
}

stack의 원리만 생각한다면 간단하다.

자료구조에 대해 이해하기 좋은 문제!

https://www.acmicpc.net/problem/1920

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_BJ_1920_수찾기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        // 이분 탐색 위한 정렬
        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        int[] find = new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++)
            find[i] = Integer.parseInt(st.nextToken());

        for(int i=0; i<m; i++) {
            //binary Search
            int low = 0;
            int high = n-1;
            int mid = 0;
            int key = find[i];
            boolean flag = false; // 탐색 성공
            while (low <= high) {
                mid = (low + high) / 2;

                if(key == arr[mid]) {
                    System.out.println(1);
                    flag = true;
                    break;
                }
                else if(key < arr[mid]){
                    high = mid-1;
                }
                else{
                    low = mid+1;
                }
            }//while
            if(!flag){
                System.out.println(0);
            }

        }//for

    }
}

이진 탐색(이분 탐색)을 연습해보려고 쉬운 문제를 골라봤다.

일단, 범위가 어마무시하기 때문에 이진 탐색이라고 생각하고 있어야 한다!!

따라서, 입력받은 것들을 배열로 오름차순으로 만들어주고, 이진탐색을 수행하면서 key가 존재하는지 살펴보면 된다.

<이진탐색 간단 정리>

1. 탐색할 배열 정렬

2. low, high, mid 값 설정

• 초기엔 low가 0, high가 맨 마지막 인덱스
• mid는 계속 갱신해나가는데 (low+high) / 2이다

3. 3가지 경우로 나눌 수 있음

• key == 배열[mid]
  • 바로 탈출하면 된다
• key < 배열[mid]
  • 찾는 값은 가운데보다 왼쪽에 존재한다는 의미
  • high = mid-1로 갱신
• key > 배열[mid]
  • 찾는 값은 가운데보다 오른쪽에 존재한다는 의미
  • low = mid+1로 갱신

4. 3의 과정을 low <= high가 될 때까지 반복하면 된다. 이 조건까지 온다면 값이 존재하지 않는다는 의미!

https://www.acmicpc.net/problem/2869

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        int day = (v - b) / (a - b);
        if((v-b)%(a-b) != 0)
            day++;
        System.out.println(day);
    }
}

이 문제는 수학적으로 생각해야했다.

일단,,, 절대로 v / (a-b)를 하면 안 된다!
목표지점에 도착한 후에는 미끄러지지 않기 때문!!

일단, 나무 길이에서 미끄러지는 길이만큼 뺐을 때(v-b)를 최종적으로 올라가는 길이(a-b)로 나눈 몫은 기본적으로 날짜에 포함된다.
이후 두 가지 경우로 나눌 수 있다.
1. 나무 길이에서 미끄러지는 길이만큼 뺐을 때, 나머지가 0
2. 나머지가 0이 아닐 때

1의 경우, 하루를 더할 필요가 없고, 2의 경우 하루를 더 더해줘야 한다!

https://www.acmicpc.net/problem/5430

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main_BJ_5430_AC {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= t; tc++) {
            StringBuilder sb = new StringBuilder();
            String p = br.readLine();
            int n = Integer.parseInt(br.readLine());
//            Deque<Character> q = new ArrayDeque<>();
            Deque<Integer> q = new ArrayDeque<>();
            StringTokenizer st = new StringTokenizer(br.readLine(),"[],");
            for(int i=0; i<n; i++) {
                q.offer(Integer.parseInt(st.nextToken()));
            }

//            안 되는 방법 : 배열에 들어갈 숫자는 최대 100이기 때문에 charAt을 사용해 끊으면 안 됨
//            30, 40이 3, 4로 끊겨 읽힘
//            String str = br.readLine();
//            for (int i = 1; i < str.length() - 1; i++) {
//                if (i % 2 == 1)
//                    q.offer(str.charAt(i));
//            }

            // deque의 앞을 보는지, 뒤를 보는지 : 앞이 true
            boolean flag = true;
            // error인지 아닌지
            boolean error = false;

            for (char command : p.toCharArray()) {
                if (command == 'R') { // 뒤집기
                    flag = !flag;
                } else { //버리기
                    if (q.isEmpty()) {
                        error = true;
                        break;
                    }

                    if (flag)
                        q.poll();
                    else
                        q.pollLast();
                }
            }//for

            if (!error) {
                sb.append("[");
                int size = q.size();
                if (flag) {
                    for (int i = 0; i < size; i++) {
                        if (i == size - 1)
                            sb.append(q.poll());
                        else
                            sb.append(q.poll()).append(",");
                    }
                } else {
                    for (int i = 0; i < size; i++) {
                        if (i == size - 1)
                            sb.append(q.pollLast());
                        else
                            sb.append(q.pollLast()).append(",");

                    }
                }

                sb.append("]").append("\n");
            }//if
            else
                sb.append("error").append("\n");

            System.out.print(sb);
        }//tc
    }//main
}

문제 자체는 어렵지 않은데,

1. 입력을 받아 [] ,를 제거하는 부분

2. 시간초과에 걸리지 않기 위해 StringBuilder를 사용하는 것

3. StringBuilder를 사용하면서 얻은 출력 형식 맞추기

이게 참 사람 발목을 잡았다.

구글링을 통해 확인하는데 어이없더라ㅋㅋㅋㅋㅋ

하여튼!! 가장 나에게 까다로웠던 1번 부분을 주석에 왜 안 되는지 적어두었다.

잊지 말자!!

https://www.acmicpc.net/problem/7569

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_BJ_7569_토마토 {
    static int box[][][];
    static int m, n, h;
    static boolean visited[][][];
    static Deque<int []> q = new ArrayDeque<>();
    // 상 하 좌 우 위 아래
    static int[] dx = {-1, 1, 0, 0, 0, 0};
    static int[] dy = {0, 0, -1, 1, 0, 0};
    static int[] dh = {0, 0, 0, 0, -1, 1};
    static int cnt = 0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        box = new int[m][n][h];
        visited = new boolean[m][n][h];

        for(int i=0; i<h; i++){
            for(int j=0; j<n; j++){
                st = new StringTokenizer(br.readLine());
                for(int k=0; k<m; k++){
                    box[k][j][i] = Integer.parseInt(st.nextToken());
                    if(box[k][j][i] == 1){
                        visited[k][j][i] = true;
                        q.add(new int[] {k, j, i});
                    }
                }
            }
        }

        bfs();
        for(int i=0; i<h; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<m; k++){
                    if(box[k][j][i] == 0) {
                        System.out.println(-1);
                        System.exit(0);
                    }
                }
            }
        }
        System.out.println(cnt-1);
    }
    public static void bfs(){
        while(!q.isEmpty()){
            int temp = q.size();
            for(int c=0; c<temp; c++) {
                int[] arr = q.poll();
                for (int i = 0; i < 6; i++) {
                    int nx = arr[0] + dx[i];
                    int ny = arr[1] + dy[i];
                    int nh = arr[2] + dh[i];

                    if (check(nx, ny, nh) && box[nx][ny][nh] == 0 && !visited[nx][ny][nh]) {
                        q.offer(new int[]{nx, ny, nh});
                        box[nx][ny][nh] = 1;
                        visited[nx][ny][nh] = true;
                    }
                }
            }
            cnt++;
        }//while
    }//bfs
    public static boolean check(int x, int y, int z){
        if(x<0 || x>=m || y<0 || y>=n || z<0 || z>=h )
            return false;
        return true;
    }
}

이와 비슷한 문제가 그냥 2차원 배열로 있던것 같은데,,, 기억이 안난다.

아마 standard로 적혀있던것 같음

별다른건 없고, 주변 토마토가 익어야 하므로 먼저 익은 토마토를 큐에 담아둔다.

그리고 bfs로 주변 토마토를 익게 하고, 익은 토마토를 큐에 다시 담으면 된다.

이때, 각 날짜별로 토마토를 모두 담은 후 토마토 개수를 센다. => 이것을 이용해서 날짜를 구분한다!

하지만, 무조건 처음에 모두 익었다면 0로 출력하라고 했으므로, -1을 하여 출력한다.

bfs를 2차원에서 3차원까지 확장하여 탐색할 수 있는지의 문제였다!

https://school.programmers.co.kr/learn/courses/30/lessons/42862

간단한 문제다.
한 15분? 정도 만에 풀었다.

오랜만에 코딩테스트 감 잡을겸 워밍업 연습~~

<풀이 코드>

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

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int[] arr = new int[n+1];
        for(int i=1; i<=n; i++){
            arr[i] = 1;
        }
        for(int i=0; i<lost.length; i++){
            arr[lost[i]]--;
        }
        for(int i=0; i<reserve.length; i++){
            arr[reserve[i]]++;
        }
        
        for(int i=1; i<n; i++){
            if(arr[i]==0){
                if(arr[i-1]==2){
                    arr[i-1]=1;
                    arr[i]=1;
                }
                else if(arr[i+1]==2){
                    arr[i+1]=1;
                    arr[i]=1;
                }
                else
                    continue;
            }
        }
        
        if(arr[n]==0){
            if(arr[n-1]==2){
                arr[n-1]=1;
                arr[n]=1;
            }
        }
        
        
        int ans = 0;
        for(int i=1; i<=n; i++){
            if(arr[i]>=1)
                ans++;
        }
        return ans;
    
    }
}

https://www.acmicpc.net/problem/17070

문제

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_17070_파이프옮기기1 {

	static int n, ans;
	static int[][] map;
	static int[] direction = {0, 1, 2};//순서대로 가로, 세로, 대각선
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}	
		} //map
		
		
		int dir = 0;
		int x=1;
		int y=2;
		route(x, y, dir);
		System.out.println(ans);
		
	}//main
	
	private static void route(int x, int y, int dir) {
		if(x == n && y==n)
			ans++;
		
		switch(dir) {
		case 0:
			// 동쪽
			if(y+1 <= n && map[x][y+1] == 0) {
				route(x, y+1, 0);
			}
			// 동남쪽
			 if(x+1 <=n && y+1<=n && map[x+1][y]==0 && map[x+1][y+1]==0 && map[x][y+1]==0) {
				 route(x+1, y+1, 2);
			 }
			break;
			
		case 1:
			//남쪽
			if(x+1 <= n && map[x+1][y] == 0) {
				route(x+1, y, 1);
			}
			//동남쪽
			if(x+1 <=n && y+1<=n && map[x+1][y]==0 && map[x+1][y+1]==0 && map[x][y+1]==0) {
				 route(x+1, y+1, 2);
			 }
			break;
		case 2:
			//동쪽
			if(y+1 <= n && map[x][y+1] == 0) {
				route(x, y+1, 0);
			}
			//남쪽
			if(x+1 <= n && map[x+1][y] == 0) {
				route(x+1, y, 1);
			}
			//동남쪽
			 if(x+1 <=n && y+1<=n && map[x+1][y]==0 && map[x+1][y+1]==0 && map[x][y+1]==0) {
				 route(x+1, y+1, 2);
			 }
			break;
		}
		
		
		
	}//route
	
}

각 방향대로 보면 된다.

0: 가로 / 1: 세로 / 2: 대각선

각 방향별로 갈 수 있는 방향이 정해져있다.

예를 들어, 가로는 동쪽과 동남쪽이 있음!!

해당하는 경우마다 범위를 계산하고, map이 0인지 아닌지를 판단한다.(문제 조건)

그리고 DFS로 계속 이동하면 됨!! 

DP로 하는 방법도 있는데, 3차원 배열을 선언해서,

각 가로, 세로, 대각선에 해당하는 것을 범위를 확인하면서 진행하고, 계속 더해나가주면 된다.