[문제링크]

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

 

0. 스네이크 게임에서 생존 시간을 구하는 문제

 

1. 초기 방향은 항상 오른쪽이므로, 주어지는 방향 전환 데이터를 통해 몇초에, 어떤 방향으로 변하는지 미리 저장한다

 

2. 머리가 진행할 때, 해당 지점에 이동 방향 정보를 저장해 두어, 꼬리가 당겨질 때의 방향을 알 수 있도록 한다

 

3. 매 초 머리를 향하는 방향으로 이동하며,

  • 사과가 나온다면 - 길이를 1 늘린다, 즉 꼬리의 길이를 줄이지 않는다
  • 빈 공간이라면 - 꼬리를 이동시킨다
  • 벽이라면 - 종료한다

 

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

public class Main{
	
	static int[][] d={
		{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}
	};
	static int[][]map;
	static int[][]move;
	static int N;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		
		map=new int[N+2][N+2];
		for (int i = 0; i < N+2; i++) {
			map[0][i]=-1;
			map[N+1][i]=-1;
			map[i][0]=-1;
			map[i][N+1]=-1;
		}
		
		int k = pint(br.readLine());
		
		for (int i = 0; i < k; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			map[ pint(st.nextToken()) ][ pint(st.nextToken()) ]=5; // 사과 위치 표시
			
		}
		int L = pint(br.readLine());
		move = new int[L][2]; // 몇초에, 어떤 방향으로 바꿀지 저장
		int dir = 3; // 초기 방향
		for (int i = 0; i < L; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			move[i][0]=pint(st.nextToken());
			//현재 방향을 보고 다음 방향 계산
			switch (st.nextToken()) {
			case "D":
				dir++;
				if(dir==5)dir=1;
				move[i][1]=dir;
				break;
			case "L":
				dir--;
				if(dir==0)dir=4;
				move[i][1]=dir;
				break;
			default:
				break;
			}
		}
		
		int time=0; //생존 시간(구하려는 답)
		int cnt=0; // 회전 횟수
		dir=3;//초기방향
		int headX=1, headY=1;
		int tailX=1, tailY=1;
		while(true) {
			time++;
			//head이동
			map[headX][headY]=dir;
			headX+=d[dir][0];
			headY+=d[dir][1];

			if(map[headX][headY]==5) {//사과면 꼬리가 한칸 늘어나는효과 = 꼬리를 줄이지 않는다
			}
			else if(map[headX][headY]!=0) {//벽이면 죽음
				break;
			}
			else {//빈칸이면 꼬리를 한칸 당긴다
				int temp = map[tailX][tailY];
				map[tailX][tailY]=0;
				tailX+=d[temp][0];
				tailY+=d[temp][1];
			}
			
			//회전
			if(cnt<L && time == move[cnt][0]) {
				dir=move[cnt][1];
				cnt++;
			}
		}
		System.out.println(time);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

5567번: 결혼식

예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대

www.acmicpc.net

 

0. 친구의 친구까지만 찾는 문제

 

1. BFS를 딱 두번만 돌린다

  • 혹은 DFS를 깊이 2에서 종료한다 (깊이 1과 2를 공유하는 node에 유의하면서)

 

2. 방문한 노드의 수 = 초대할 사람의 수이다

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int M = pint(br.readLine());
		ArrayList<ArrayList<Integer>>graph = new ArrayList<>();
		
		for (int i = 0; i < N; i++)graph.add(new ArrayList<>());
		boolean[]isV = new boolean[N];
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken())-1;
			int y = pint(st.nextToken())-1;
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		
		//1부터 시작해, 2번 안에 갈수있는 사람의 수 찾기
		int count=0; //몇번 건넌 친구인지 = 몇 번 돌았는지
		int friendCnt=0;
		Queue<Integer>qu = new LinkedList<Integer>();
		qu.offer(0); //초기 node = 자기 자신
		isV[0]=true;
		while(count<2) {
			int len =qu.size();
			for (int i = 0; i < len; i++) {
				int curNode = qu.poll();
				
				int graphLen = graph.get(curNode).size();
				for (int j = 0; j < graphLen; j++) {
					int nextNode = graph.get(curNode).get(j);
					if(!isV[nextNode]) {
						friendCnt++;
						isV[nextNode]=true;
						qu.offer(nextNode);
					}
				}
				
			}
			
			count++;
		}
		System.out.println(friendCnt);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

14719번: 빗물

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치

www.acmicpc.net

0. 위 그림과 같이 높이를 하나씩 받으며 스택에 저장하고, 해당 입력으로 인해 발생한 빗물 공간을 구해 누적한다

 

1. 입력 x가 들어왔을때, 스택에 자기보다 작은 값이 있다면, 빗물 공간이 발생할 수 있다

  • 위 그림처럼 6 0 4 0 3 0 0 5 순으로 입력이 들어왔을때, 3과 5 사이에는 공간이 발생한다 (빨강)
  • 그 다음 4와 5 사이에도 공간이 발생했는데, 이전에 3까지의 높이는 처리했으므로 4 높이에 대해서만 공간이 생긴다 (노랑)
  • 이전에 처리한 높이를 prevCnt로 저장, 사용한다
  • 공간이 계속해 발생할 수 있으므로, 스택을 계속 따라간다

 

2. 스택에 자기보다 큰 값이 있다면, 역시 공간이 발생할 수 있다

  • 6과 4 사이에서 공간이 발생한다 (파랑)
  • 이때 생성되는 공간의 높이는 입력 x에서 이전 처리값 prevCnt를 뺀 값이다
    • 위 그림에서 초록색 부분은, 입력 x는 5이고 prevCnt는 4이므로 높이는 1이다
  • 자기보다 큰 값을 만났으므로, 공간이 계속해서 발생할 수 없으니 종료한다

 

3. 위 방식으로 공간의 높이는 구할 수 있다

  • 공간의 너비를 구하기 위해, 스택에 저장할 때 값뿐 아닌 해당 지점의 x좌표도 함께 저장한다
  • 두 좌표를 비교해 너비를 구하여, 높이와 곱해 총 빗물 공간의 면적을 구한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
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 H = pint(st.nextToken());
		int W = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		Stack<int[]> stack = new Stack<>();
		int area=0;
		
		for (int i = 0; i < W; i++) {
			int input = pint(st.nextToken());
			
			int prevMax=0, sum=0;
			while(!stack.isEmpty() && stack.peek()[0]<=input) {
				int[] tmp = stack.pop();
				
				if(tmp[0]>prevMax) {
					int height = tmp[0]-prevMax;
					prevMax=tmp[0];
					sum+= height*( i-tmp[1]-1 );
				}
				
			}
			
			if(!stack.isEmpty()) {
				int[] tmp = stack.peek();
				int height = input - prevMax;
				sum+= height*(i-tmp[1]-1);
			}
			
			area+=sum;
			// 스택에 넣기
			stack.add(new int[] {input,i});
			
		}
		System.out.println(area);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

[문제링크]

 

11062번: 카드 게임

근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는

www.acmicpc.net

 

0. 번갈아가며 양쪽 끝에서 한장씩 집을때 최대한 많은 점수를 얻는 방법

 

1. x~y까지의 카드에서 최대한 많은 점수를 얻으려면 card[y] + (x~y-1) 혹은 card[x] + (x+1~y)중 큰 값으로 고를 수 있다

 

2. 이때, 각자 서로의 점수를 위해 최선의 전략을 사용하고, 서로 가져갈수 있는 카드의 총합은 동일하다

  • 따라서, 후 플레이어의 최선의 전략 = 선 플레이어의 점수를 가능한 낮추는 전략 과 같다

 

3. DP테이블을 2중으로 만들어, (x, y) 만큼의 카드 상태에서 선 플레이어/후 플레이어 각각의 최선의 결과를 저장한다

  • 후 플레이어의 선택은 선 플레이어의 점수와는 관계없으므로 저장하지 않는다

 

4. 모든 테이블이 완성된 후, 모든 카드에 대해 선 플레이어의 점수를 출력한다

 

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));
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			int N = pint(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] card = new int[N];
			int[][][]dp = new int[N+1][N+1][2];
			
			for (int i = 0; i < N; i++) {
				card[i]=pint(st.nextToken());
			}
			
			for (int i = 0; i < N; i++) {
				dp[i][i][0]=card[i];
				dp[i][i][1]=0;
			}
			
			//i~i+len 까지의 카드를 고려했을때, 근우가 얻을수 있는 최대 점수
			for (int len = 1; len < N; len++) {
				
				for (int i = 0; i < N-len; i++) {
					//i : 시작점, len : 길이
					int j = i+len;
					//근우턴일때 근우 최대점수 = 왼/오 각 경우중 최댓값 + 카드 선택값
					dp[i][j][0]=Math.max(card[j]+dp[i][j-1][1], card[i]+dp[i+1][j][1]);
					//명우턴일때 근우 최대점수 = 왼/오 각 경우중 최솟값 (카드 선택 못함)
					dp[i][j][1]=Math.min(dp[i+1][j][0], dp[i][j-1][0]);
				}
			}
			System.out.println(dp[0][N-1][0]);			
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글

[백준] 2075 - N번째 큰 수  (0) 2021.08.27
[백준] 3190 - 뱀  (0) 2021.08.08
[백준] 14719 - 빗물  (0) 2021.08.08
[백준] 2600 - 구슬게임  (0) 2021.07.31
[백준] 16472 - 고냥이  (0) 2021.07.25
[백준] 20366 - 같이 눈사람 만들래?  (0) 2021.07.25
[백준] 2026 - 소풍  (0) 2021.07.11

[문제링크]

 

2600번: 구슬게임

첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개의 정수 b1, b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다.

www.acmicpc.net

 

0. 두 상자에 x,y개의 구슬이 있고, b1,b2,b3 중 하나만큼 구슬을 꺼낼 수 있을때, 최종 승자를 찾는 문제

 

1. (x, y)에서 시작해 b1, b2, b3를 빼는 경우의 수 전체를 고려했을때, 단 하나라도 승리하는 경우가 있다면 승리한다

 

2. 반대로, 모든 경우의 수가 패배라면, 패배한다

 

3. 선제공격이 이기는 경우를 true, 지는 경우를 false로 둔다

 

4. 최소 선택 단위인 b1보다 구슬의 수가 적다면 선택할수 없으므로 패배한다, 이를 기초로 DP 진행

 

5. 선공인 A가 어떠한 선택을 하여 구슬 상태가 (x', y')로 변했는데, DP[x'][y']가 선공 승리인 상태라면, A는 패배한다

  • (x', y')상태에서는 턴이 넘어가 B가 선공이 되기 때문
  • 즉, DP[x'][y']로 진행할 경우 현재 상태인 DP[x][y]에서의 결과는 !DP[x'][y']가 된다

 

6. DP 테이블이 완성되면 구한 결과 출력

 

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 b1 = pint(st.nextToken());
		int b2 = pint(st.nextToken());
		int b3 = pint(st.nextToken());
		
		boolean[][]dp = new boolean[501][501];
		
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp.length; j++) {
				if(i>=b1&&j>=b1) {
					//어떤 선택을 하더라도 상대 승리
					if(dp[i-b1][j] && dp[i][j-b1])dp[i][j]=false;
					//내가 이기는 선택지가 존재
					else dp[i][j]=true;
				}
				else if(i>=b1)dp[i][j]=!dp[i-b1][j];
				else if(j>=b1)dp[i][j]=!dp[i][j-b1];

				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b2&&j>=b2) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b2][j] && dp[i][j-b2])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b2)dp[i][j]=!dp[i-b2][j];
					else if(j>=b2)dp[i][j]=!dp[i][j-b2];
				}
				
				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b3&&j>=b3) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b3][j] && dp[i][j-b3])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b3)dp[i][j]=!dp[i-b3][j];
					else if(j>=b3)dp[i][j]=!dp[i][j-b3];
				}
			}
		}
		 
		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int k1 = pint(st.nextToken());
			int k2 = pint(st.nextToken());
			
			System.out.println(dp[k1][k2]?'A':'B');
			
		}
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글

[백준] 3190 - 뱀  (0) 2021.08.08
[백준] 14719 - 빗물  (0) 2021.08.08
[백준] 11062 - 카드게임  (0) 2021.07.31
[백준] 16472 - 고냥이  (0) 2021.07.25
[백준] 20366 - 같이 눈사람 만들래?  (0) 2021.07.25
[백준] 2026 - 소풍  (0) 2021.07.11
[백준] 3967 - 매직스타  (0) 2021.07.11

[문제링크]

 

16472번: 고냥이

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고

www.acmicpc.net

 

0. n글자 이내로 이루어진 가장 긴 연속된 문자열 찾기

  • 투 포인터로 n글자를 유지하면서 진행한다

 

1. n+1글자가 되어 읽을 수 없을때까지 snd 포인터를 진행, 문자열을 늘린다

  • 최장 문자열 길이를 갱신한다

 

2. 다시 n글자가 되어 읽을 수 있을때까지 fst 포인터를 진행, 문자열을 줄인다

 

3. snd가 끝에 도달하여 종료되었을때, 가장 길었던 문자열의 길이가 정답

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		String s = br.readLine();
		
		int maxLen=0;
		int len = 0;
		int[] cnt = new int[26];
		int kindCnt=0;
		
		int fst=0, snd=0;
		
		while(fst<=snd && snd<s.length()) {
			//1. N글자+1까지 snd 늘리면서 len 비교저장
			while(snd<s.length() && kindCnt<=N) {
				int cur = s.charAt(snd++)-'a';
				if(cnt[cur]==0)kindCnt++;
				cnt[cur]++;
				len++;
				//N+1글자일 때는 len을 갱신하면 안된다 
				if(kindCnt<=N)maxLen=Math.max(maxLen, len);
			}
			//2. N글자까지 fst 줄이기
			
			while(fst<=snd && kindCnt>N) {
				int cur = s.charAt(fst++)-'a';
				cnt[cur]--;
				if(cnt[cur]==0)kindCnt--;
				len--;
			}
			
		}
		System.out.println(maxLen);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면

'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글

[백준] 14719 - 빗물  (0) 2021.08.08
[백준] 11062 - 카드게임  (0) 2021.07.31
[백준] 2600 - 구슬게임  (0) 2021.07.31
[백준] 20366 - 같이 눈사람 만들래?  (0) 2021.07.25
[백준] 2026 - 소풍  (0) 2021.07.11
[백준] 3967 - 매직스타  (0) 2021.07.11
[백준] 9663 - NQueen  (0) 2021.07.11

[문제링크]

 

20366번: 같이 눈사람 만들래?

높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1

www.acmicpc.net

 

0. N 범위가 600이므로, O(N^3)까지 실행 가능하다

  • O(N^2)로 엘사가 만들 수 있는 모든 눈사람 만들기
  • O(N)으로 엘사의 눈사람에 가장 가까운 안나의 눈사람 찾기 (투 포인터 사용)

 

1. 두 눈덩이를 선택해 엘사의 눈사람을 만든다

  • 크기가 큰 아래 눈덩이를 선택하고, 그 다음 위 눈덩이를 선택한다
  • 이를 위해 입력값을 크기순으로 정렬해 사용

 

2. 엘사의 눈사람과 가장 가깝게 안나의 눈사람을 만든다

  • 양쪽 끝 눈덩이(가장 큰/가장 작은)를 선택하면서 시작
  • 안나의 눈사람이 더 크면 : 더 작아져야 한다 - 큰 눈덩이(위)를 한단계 더 작은 눈덩이로 교체
  • 안나의 눈사람이 더 작으면 : 더 커져야한다 - 작은 눈덩이(아래)를 한단계 더 큰 눈덩이로 교체
  • 두 눈사람의 크기가 같아지거나 / 안나의 눈사람의 위/아래 눈덩이가 교차하면 종료

 

3. 안나의 눈사람마다 갱신한 min값이 정답

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int[]snow=new int[N];
		int min=Integer.MAX_VALUE;
		
		for (int i = 0; i < N; i++) {
			snow[i]=pint(st.nextToken());
		}
		
		Arrays.sort(snow);
		
		for (int elsaFst = 0; elsaFst < N; elsaFst++) {
			//아래쪽
			for (int elsaSnd = 0; elsaSnd < elsaFst; elsaSnd++) {
				//위쪽
				int elsaSnow = snow[elsaFst]+snow[elsaSnd];
				int fst=0,snd=N-1;
				
				//안나의 눈사람이 더 크면 - snd를 줄인다
				//더 작으면 - fst를 늘린다
				
				while(fst<snd) {
					if(fst==elsaFst || fst==elsaSnd) {
						fst++;continue;
					}

					if(snd==elsaFst || snd==elsaSnd) {
						snd--;continue;
					}
					
					int annaSnow = snow[fst]+snow[snd];
					min=Math.min( min, Math.abs(annaSnow-elsaSnow) );
					
					if(annaSnow>elsaSnow) {
						snd--;
					}
					if(annaSnow<elsaSnow) {
						fst++;
					}
					if(annaSnow==elsaSnow) {
						break;
					}
					
					
				}
				
			}
		}
		
		System.out.println(min);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면

'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글

[백준] 11062 - 카드게임  (0) 2021.07.31
[백준] 2600 - 구슬게임  (0) 2021.07.31
[백준] 16472 - 고냥이  (0) 2021.07.25
[백준] 2026 - 소풍  (0) 2021.07.11
[백준] 3967 - 매직스타  (0) 2021.07.11
[백준] 9663 - NQueen  (0) 2021.07.11
[백준] 2109 - 순회강연  (0) 2021.07.07

@DynamicInsert
@DynamicUpdate

 

어노테이션을 클래스 상단에 붙여주면 null 값은 insert/update문에 들어가지 않게 된다

+ Recent posts