개발자-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/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 버튼을 누를 때마다 for문을 순회하며 구현 할 수도 있는 문제이다. 주어진 조건을 보면 아래와 같은 점화식을 세울 수 있다. import java.io.*; import java.util.*; public class Main { public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); p..

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/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 백트랙킹을 이용하여 수어진 배열의 모든 가지수를 구한다. 주어진 수식으로 답을 구한 뒤 답중 최대 값을 출력한다. import java.io.*; import java.util.StringTokenizer; public class Main { private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); privat..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 주어진 좋은 수열을 만족하는 경우에만 123 탐색을 진행했다. 123 중복을 허용하는 순으로 진행했기 때문에 가장 작은 수는 가장 첫 번째 발견되는 수열이다. import java.io.*; public class Main { private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static..

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 ..