개발자-H 입니다.

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 백트래킹 완전탐색으로 구할 수 있는 문제이다. 초반에 시간 초과로 꾀 고생을 했는데 집을 선택하는 순서는 관계 없기 때문에 오름 차순 식으로 풀면 통과 할 수 있다. 결론적으로 아래의 문제에서 입력 형식과 결과 도출만 달라진 문제였다. N과 M(2) import java.io.*; import java.util.*; public class Main { public static..

https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 백트래킹 탐색 문제이다. 3대 500 이하 일시 바로 탐색을 종료해버리면 된다. import java.io.*; import java.util.*; public class Main { public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static int N..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 백트래킹 탐색 문제이다. 처음에는 주어진 입력 문자열을 String.IndexOf를 사용하여 완탐했으나 10이 넘어가는 시점에서 탐색 개수가 기하급수 적으로 늘어나 시간 초과를 받았다. 문제에서 주어진 조건으로 최대 N!이 50이 넘지 않기에 1~ 2 길이를 이용하여 만들 수 있는 모든 문자열을 검색하는 것으로 바꾸었다. import java.io.BufferedReader; ..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 기본적인 완전 탐색이다. 해당 문제를 풀며 실행 속도에 대해 조금 고민을 했었는데 최적화 결과는 사진과 같다. 재귀 함수 파라메터를 전역변수로 옮김 (548 -> 316) StringBuilder.append 함수를 " " -> ' '로 변경 (316->256) Java에서 " "는 String Class 를 생성하는 것 같다. import java.io.*; import java.util.*; public class Main { public static final BufferedRea..

https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 백트래킹을 활용한 완전 탐색 문제이다. 주어진 포지션의 개수와 플레이어 포지션 별 능력을 활용하여 완전 탐색 후 최대 값을 구하면 된다. import java.io.*; import java.util.*; public class Main { private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static ..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹 + 배열 조작 문제이다. 처음에는 각 DP 마다 모든 배열을 검사하도록 수행했더니 시간 초과가 나버렸다. 배열 검사는 가장 마지막에 오는 DP만 검사하여 조건에 맞는 색종이를 사용했는지 확인했다. import java.io.*; import java.util.*; public class Main { private static BufferedReader br = new Buffer..

https://www.acmicpc.net/problem/1174 1174번: 줄어드는 숫자 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어 www.acmicpc.net 백트래킹 탐색 문제이다. 총 1023가지 경우의 수가 나온다. 첫 번째가 1부터 시작함에 주의한다. 다음 탐색 조건을 앞의 숫자와 비교하여 작을 시 탐색한 뒤 주어진 번째 수가 맞다면 탈출 하는 방법을 사용했다. import java.io.*; import java.util.*; public class Main { private static BufferedReader br = ne..