PS/백준

[문제 링크]https://www.acmicpc.net/problem/15686문제 설명0-빈칸, 1-집, 2-치킨집 치킨거리 = 집(x1, y1)과 가장 가까운 치킨집(x2, y2) 사이의 거리 → |(x1-x2)| + |(y1-y2)|도시의 치킨거리 = 모든 집의 치킨 거리의 합 치킨집을 최대 m개를 골랐을 때, 도시의 치킨거리의 최소값을 구한다. 문제 풀이도시에 대한 정보를 입력받으면서 치킨집과 집의 위치 정보를 리스트에 따로 저장한다.dfs() : dfs 알고리즘을 사용해서 m개의 치킨집을 고른다. 이 때, 치킨집의 위치를 따로 저장한 리스트를 사용해서 m개의 치킨집을 고른다.cityChicken() : houseChicken() 에서 구한 치킨거리를 모두 더해서 도시의 치킨거리를 구한다..

[문제 링크]https://www.acmicpc.net/problem/6603문제 설명하나의 테스트 케이스에 k와 k개의 수로 이루어진 집합 S를 입력받는다.집합 S에서 6개의 수를 고르는 방법을 사전순으로 모두 출력한다. 6개의 수를 고를 때, 숫자의 순서는 상관없다. 문제 풀이백트래킹 풀이cnt = 고른 숫자의 개수, start = 반복문 시작 인덱스start ~ k 를 돌면서 숫자를 하나씩 선택한 후, 재귀호출 한다. 재귀 호출을 할 때는 현재 선택한 수의 바로 다음 위치부터 탐색을 시작하도록 start = i + 1 로 설정한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;..

[문제 링크]https://www.acmicpc.net/problem/15649문제 설명자연수 N과 M이 주어졌을 때, '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열'을 모두 구하는 프로그램을 작성하시오 입력자연수 N과 M(1 출력사전 순으로 증가하는 순서로 수열 출력입출력 예시입력예시출력예시3 11234 21 21 31 42 12 32 43 13 23 44 14 24 3 문제 풀이DFS를 사용해서 백트래킹 풀이재귀 호출을 통해서 1 ~ n까지 돌면서 중복없이 m개의 수를 탐색한다.종료 조건 : count가 m과 같으면 해당 수열을 출력하고 재귀 호출 종료(1) ArrayList 사용(나의 풀이)ArrayList의 contains() 함수를 사용해서 중복체크를 하고, 재귀가 종료되면 A..

[문제 링크]https://www.acmicpc.net/problem/11053문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기둘째 줄에 수열 A를 이루고 있는 원소들출력가장 긴 증가하는 부분 수열의 길이입출력 예시입력예시출력예시610 20 10 30 20 504 문제 풀이다이나믹 프로그래밍으로 풀이dp[i] : array[i]를 마지막 값으로 가지는 증가 부분 수열들 중에서 가장 긴 부분수열의 길이array[i]가 어떠한 증가 부분 수열의 마지막 값이 되려면, ar..

[문제 링크]https://www.acmicpc.net/problem/2579문제 설명계단 오르기 게임은 계단 아래 시점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다.1. 계단은 한 번에 한 계단 or 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면 이어서 다음계단이나, 다음다음계단을 밟은 수 있다.2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 포함되지 않음3...

[문제 링크]https://www.acmicpc.net/problem/10026문제 설명적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못해서 적록색약이 아닌 사람이 보는 그림과 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나누어지며, 하나의 구역은  상하좌우로 인접해있는 같은 색상일 경우 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록..