백준

3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 풀이 어떻게 풀까 고민하다가 보드의 크기가 50이하로 작고 다른 생각이 떠오르지 않았기 때문에 완전탐색으로 모든 경우의 수를 체크해보았습니다. 모든 인접한 위치의 사탕을 바꾸고 확인해봐도 되지만 아래와 우측만 교체하여 비교하더라도 모든 경우의 수를 체크할 수 있기 때문에 아래와 우측만 교환하여 비교하고 다시 제자리로 돌리고를 반복했습니다. 1, 1에서 왼쪽과 위쪽으로 교체하지 않아도 되는 이유는 1,0에서 우측, 0, 1에서 아래를 교체했을 때와 동일한 상황이기 때문..

22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 문제 유사 중위 순회를 하면서 이동한 총 횟수를 출력한다. 풀이 유사 중위 순회를 하면서 이동한 총 횟수를 출력해야 하는데, 여기서 주의할 점은 유사 중위 순회의 종료지점이 일반 중위 순회의 종료 지점일 경우에 종료해야 한다는 점이다. 유사 중위 순회의 종료 지점이 모든 노드를 방문했을 경우로 착각해서 여기서 많이 당황했다. 따라서 문제를 잘 읽어보길 바란다. 📌 값 입력 StringTokenizer st; for(int i=1; i

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오. 풀이 이진 탐색 트리의 전위 순회한 결과가 주어졌을 때, 트리를 후위 순회해야 하기 때문에 먼저 전위순회한 결과를 이진 탐색트리로 바꿔주었고 바꾼 트리를 다시 후위 순회하여 결과를 출력하였습니다. 📌 값 입력받기 String value = ""; while (true){ value = br.readLine(); if(value == ..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 풀이 이 문제는 DP 문제로 주어진 직사각형 크기를 가득 채우는 방법의 수를 물어본다. 따라서 작은 크기의 사각형부터 하나씩 방법들을 작성하면서 어떤 규칙이 있는지 생각해보고 점화식을 만들었다. n = 1, 일때 방법은 1가지 n = 2, 일때 방법은 2가지 n = 3, 일때 방법은 3가지 n = 4, 일때 방법은 5가지 n = 5, 일때 방법은 8가지 위의 결과를 보고 유추해보다가..

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 풀이 이친수의 첫 자리수는 1이 반드시 와야하기..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. 풀이 1번 컴퓨터와 연결된 모든 컴퓨터를 DFS 혹은 BFS로 탐색하면서 감염된 컴퓨터를 구하는 문제였다. 📌 입력 int N = Integer.parseInt(br.readLine())+1; int M = Integer.parseInt(br.readLin..

14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 풀이 로봇 청소기가 동작하는 방식을 BFS 로직과 비슷하게 구현해보았습니다. 📌 입력 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine())..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로..