구르는 돌에는 이끼가 끼지 않는다

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

package com.ji.beakjoon.dp;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

/**
 * 출석체크
 * @author ji
 *
 */
public class AttendanceCheck {
	static int add;
	static boolean[] sleep, chk;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] studentInfo = br.readLine().split(" ");
		int N = Integer.valueOf(studentInfo[0]); //학생의 수
		int K = Integer.valueOf(studentInfo[1]); //졸고 있는 학생의 수 
		int Q = Integer.valueOf(studentInfo[2]); //출석 코드를 보낼 학생의 수
		int M = Integer.valueOf(studentInfo[3]); //주어질 구간의 수
		
		int[] dp = new int[N+3];
		for(int i=3; i<= N+2; i++) {
			dp[i] = i;
		}
		
		// 	(1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000)
		sleep = new boolean[5005];
		chk = new boolean[5005];
		
		//졸고 있는 학생 초기화
		String[] sleepInfo = br.readLine().split(" ");
		for(int i=0; i < K; i++) {
			int sleepStudentNum = Integer.valueOf(sleepInfo[i]);
			sleep[sleepStudentNum] = true;
		}
		
		//출석 코드를 보낼 학생의 수 
		String[] qrInfo = br.readLine().split(" ");
		for(int i=0; i < Q; i++) {
			int qrStudentNum = Integer.valueOf(qrInfo[i]);
			if(sleep[qrStudentNum]) continue;//출석 코드는 받았으나 졸았을 경우 패스
			add = qrStudentNum; //출석 코드를 받은 학생 입장 번호
			while(qrStudentNum <= N+2) { 
				if(sleep[qrStudentNum]) {
					qrStudentNum += add;
					continue;
				}
				chk[qrStudentNum] = true;//출석 코드를 받을 학생 정보를 chk배열에 저장
				qrStudentNum += add;//배수인 학생!!
			}
		}
		
		for(int i=3; i<= N+2; i++) {
			int unAttend = (!chk[i])?1:0;//출석 되지 않은 학생 수 dp에 계산
			dp[i] = dp[i -1] + unAttend;
		}
		
		for(int i=0; i < M; i++) {
			String[] MInfo = br.readLine().split(" ");
			int s = Integer.parseInt(MInfo[0]);
			int e = Integer.parseInt(MInfo[1]);
			System.out.println(dp[e] - dp[s-1]); //구간에 해당하는 출석이 되지 않은 학생 수 출력
		}
		
		br.close();
		bw.flush();
		bw.close();
		
	}

}

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

package com.ji.beakjoon.dfs;

import java.util.Scanner;

/**
 * 징검다리 건너기
 * 
 * @author ji
 *
 */
public class CrossingBridgeDfs {

	static int[][] arr;
	static int stoneCount;
	static boolean done = true;
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		stoneCount = input.nextInt();
		arr = new int[stoneCount - 1][2];
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < 2; j++) {
				arr[i][j] = input.nextInt();
			}
		}
		int k = input.nextInt();
		int sum = 0;
		dfs(1, k, done, sum);
		System.out.println(min);
	}

	public static void dfs(int personPosition, int k, boolean done, int sum) {
		if (personPosition == stoneCount) {//영재의 위치가 돌의 위치에 일치할 경우만
			min = Math.min(min, sum);
			return;
		} else if (personPosition < stoneCount) {//영재의 위치가 아직 돌을 못넘었을경우

			// 매우 큰 점프
			if (done == true) {//매우 큰점프는 한번만 동작
				sum += k;
				done = false;
				dfs(personPosition + 3, k, done, sum); 
				sum -= k;
				done = true;
			}

			// 작은 점프 값으로 sum증가 후 재귀
			sum += arr[personPosition - 1][0];
			dfs(personPosition + 1, k, done, sum);
			sum -= arr[personPosition - 1][0];

			// 큰 점프 값으로 sum 증가 후 재귀
			sum += arr[personPosition - 1][1];
			dfs(personPosition + 2, k, done, sum);
			sum -= arr[personPosition - 1][1];
		}

	}
}

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

package com.ji.beakjoon.bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SavePrincess {
	static int N, M, T;
	static int map[][];
	static int dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};
	static int ret;
	static class Pair{
		int r,c,time;
		int item;
		
		public Pair(int r, int c,  int item, int time) {
			super();
			this.r = r;
			this.c = c;
			this.time = time;
			this.item = item;
		}
		
	}
	
	static ArrayList<Pair> list;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		T = Integer.valueOf(st.nextToken());
		map = new int[N][M];
		ret = 0;
		for(int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.valueOf(st.nextToken());
			}
		}
		bfs();
		if(ret!=0)
			System.out.println(ret);
		else
			System.out.println("Fail");
	}
	private static void bfs() {
		boolean visit[][][] = new boolean[2][N][M]; //검 유무, 세로, 가로
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(0,0,0,0));
		visit[0][0][0] = true;
		while(!q.isEmpty()) {
			Pair cur = q.poll();
			if(cur.r == N-1 && cur.c == M-1) {
				if(cur.time <= T)
					ret = cur.time;
				break;
			}
			if(cur.time > T)
				break; 
			for(int i=0; i<4; i++) {
				int nr = cur.r+dr[i];
				int nc = cur.c+dc[i];
				if(nr<0||nc<0||nr>=N||nc>=M||visit[cur.item][nr][nc]) continue;
				
				//방문하지 않고 아이템이 없는 경우
				if(cur.item==0) {
					
					if(map[nr][nc] == 0) {
						visit[0][nr][nc] = true;
						q.add(new Pair(nr,nc,0, cur.time +1));
					}else if(map[nr][nc]==2) {
						visit[1][nr][nc]=true;
						q.add(new Pair(nr,nc, 1, cur.time+1));
					}
					
				}else {//방문하지 않고 아이템이 있는 경우 벽 뚫기 가능
					if(map[nr][nc]==1||map[nr][nc]==0) {
						visit[1][nr][nc]=true;
						q.add(new Pair(nr,nc, 1, cur.time+1));
					}
				}
				
			}
		}
		
	}

}