map[m][n] 위치로 이동하기까지의 이동 경로의 수를 구하기 위해 임의의 위치에서 m, n까지 이동경로의 개수를 dp테이블을 통해 계산한다.
임의의 x, y에 대한 dp[x][y]는 dp[x+1][y]+dp[x][y+1]+dp[x-1][y]+dp[x][y-1]과 같다.
다만 이미 dp가 초기값이 아닌 경우 혹은 범위를 벗어난 경우는 예외로 한다.
단순히 dfs만을 사용하여 위 문제를 해결할 경우 모든 경우의 수에 대해 실행하였을 때
4방향으로 칸을 이동하고 최대범위가500*500이므로
4^(500*500) 개의 경우의 수를 실행하게 됨으로 인해 시간초과로 해결 할 수 없다.
코드
#include<iostream>
#include<cstring>
using namespace std;
int M, N;
int map[500][500]; //지도 내 높이 저장
int dp[500][500]; //해당 지점에서의 이동 경로 저장
int xi[4] = { 1,0,-1,0 }; //좌 , 우
int yi[4] = { 0, 1, 0, -1 }; // 하, 상
int DFS(int m, int n) {
//해당 지점이 목표 지점인 경우 탐색 종료
if (m == M-1 && n == N-1) {
return 1;
}
//해당 지점이 이미 탐색이 진행된 경우 탐색 종료
if (dp[m][n]!=-1) {
return dp[m][n];
}
//현재 방문한 지점을 -1-> 0으로 초기화
dp[m][n] = 0;
//해당 지점에서 상 하 좌 우 이동을 통해 현재 지점까지의 경로 탐색
for (int i = 0; i < 4; i++)
{
if (m + xi[i] >= 0 && m + xi[i] < M && n+ yi[i]>=0 && n + yi[i] < N)
{
if (map[m][n] > map[m + xi[i]][n + yi[i]]) {
//해당 지점까지의 이동 경로의 수는 다음 이동 경로의 DFS결과의 합으로 저장
dp[m][n]+=DFS(m + xi[i], n + yi[i]);
}
}
}
return dp[m][n];
}
int main()
{
cin >> M >> N;
int tmp=0;
for (int i = 0; i < M; i++){
for (int j = 0; j < N; j++){
cin >> tmp;
map[i][j] = tmp;
}
}
memset(dp, -1, sizeof(dp));
cout << DFS(0, 0) << endl;
return 0;
}
물이 처음 새는 곳의 위치에 테이프가 붙여질 것이고 좌우 0.5 만큼의 범위를 주어야 한다.
(새롭게 테이프가 붙여진 곳 - 0.5) 부터 (새롭게 테이프가 붙여진 곳 + 테이프의 길이 - 0.5)
범위 내에 포함되어 있는 위치는 테이프를 통해 가릴 수 있다.
이 때 범위를 벗어난 곳에 물이 새는 경우 새로운 테이프를 붙이고 다시 범위를 정하여 총 필요 테이프의 개수를 정한다.
코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, L;
vector<float> leakPoint;
int main() {
//input
int tmp;
cin >> N >> L;
for (int i = 0; i < N; i++) {
cin >> tmp;
leakPoint.push_back(tmp);
}
//물이 새는 곳의 위치를 정렬
sort(leakPoint.begin(), leakPoint.end());
float range = 0;
int answer = 0;
//물이 새는 곳의 위치로부터 -0.5+테이프의 길이를 테이프로 가릴수있는 범위 : range 로 설정하고
//leakPoint배열에서 range를 벗어난 경우에는 다시 그 포인트를 기준으로 range를 설정하여
//새롭게 기준이 선정되어 새로운 테이프를 붙이게 되는 경우 answer++를 통해 총 필요한 테이프의 개수를 저장
for (int i = 0; i < N; i++)
{
if (leakPoint[i]+0.5 > range){
range = leakPoint[i] - 0.5 + L;
answer++;
}
}
//print
cout << answer << endl;
return 0;
}
DFS(tmpSum, idx + 1); //현재 인덱스의 수를 더하지 않은 결과로 다시 진행 DFS(sum, idx + 1); //현재 인덱스의 수를 더한 상태로 다시 진행
DFS함수 내에서 모든 경우의 수를 탐색하도록 하였다.
코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
int S = 0;
int N = 0;
int answer = 0;
void DFS(int sum, int idx)
{
//arr의 범위를 벗어난 경우에는 함수 종료
if (idx >= N)
{
return;
}
//현재의 인덱스의 수를 더하기 전의 상태를 tmpSum에 저장
int tmpSum = sum;
sum += arr[idx];
if (sum== S) {
answer++;
}
DFS(tmpSum, idx + 1); //현재 인덱스의 수를 더하지 않은 결과로 다시 진행
DFS(sum, idx + 1); //현재 인덱스의 수를 더한 상태로 다시 진행
}
int main()
{
int tmp = 0;
//input
cin >> N >> S;
for (int i = 0; i < N; i++) {
cin >> tmp;
arr.push_back(tmp);
}
DFS(0, 0);
//정답 출력
printf("%d", answer);
return 0;
}
n의 크기가 최대 50인 정사각형 형태의 배열에 주어진 사탕 중 두개의 사탕의 위치를 바꾸었을 때 행이나 열중에 가장 긴 연속 부분을 찾는 문제이다.
중첩 for문을 통해 배열 내의 모든 경우의 수를 찾아보는 brute-force 방식을 사용하였다.
코드
//백준 3085번
//for(for)문으로 한개씩 전부 좌우로 바꿔본 후에 체크
//for(for)문으로 한개씩 전부 상하로 바꿔본 후에 체크
//체크 시 가로로 가장 긴 것 한번 세로로 가장 긴 것 한번 체크
//모두 다 종합하여 가장 긴 것을 답으로 채택
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MAX 50
int N;
string board[MAX];
//출력할 답을 저장
int answer = 1;
void solution() {
//가로로 가장 긴 것 체크
for (int i = 0; i < N; i++)
{
int sum = 1;
for (int j = 1; j < N; j++){
if (board[i][j-1] == board[i][j])
sum++;
else {
if(answer < sum)
answer = sum;
sum = 1;
}
}
//j가 N까지 확인하였을 때 하나가 추가된 경우
//else문으로 들어가지 못하므로 이곳에서 체크
if (answer < sum)
answer = sum;
}
//세로로 가장 긴 것 체크
for (int i = 0; i < N; i++)
{
int sum = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[j][i] == board[j+1][i])
sum++;
else {
if (answer < sum)
answer = sum;
sum = 1;
}
}
//j가 N까지 확인하였을 때 하나가 추가된 경우
//else문으로 들어가지 못하므로 이곳에서 체크
if (answer < sum)
answer = sum;
}
}
int main()
{
//input
cin >> N;
for (int i = 0; i < N; i++)
cin >> board[i];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N-1; j++)
{
//좌우로 하나씩 바꿔가면서 체크
swap(board[i][j], board[i][j + 1]);
solution();
swap(board[i][j], board[i][j + 1]);
//상하로 하나씩 바꿔가면서 체크
swap(board[j][i], board[j+1][i]);
solution();
swap(board[j][i], board[j + 1][i]);
}
}
cout << answer << endl;
return 0;
}
//백준 2503 숫자야구
#pragma warning(disable:4996)
#include<stdio.h>
#include<iostream>
#include<vector>
#include <string>
#include <tuple>
#include<cstring>
using namespace std;
struct inputData
{
int question;
int strike;
int ball;
};
int n;
inputData* arr = new inputData[n];
bool checkIn[987];
void input() {
int tmp;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i].question);
scanf("%d", &arr[i].strike);
scanf("%d", &arr[i].ball);
}
}
int main() {
//chekIn-> 1로 초기화
memset(checkIn, 1, sizeof(checkIn));
input();
string check;
string checkList;
int checkStrike = 0;
int checkBall=0;
//n개의 질문에대하여
//k[123~987] 까지의 질문에 대하여 각각 비교해보고 끝까지 true남은 것만 답으로 체크
for (int i = 0; i < n; i++) {
for (int k = 123; k <= 987; k++) {
//현재 질문의 숫자와 k 번째 숫자의 질문을 비교
check=to_string(arr[i].question);
checkList = to_string(k);
//k번째 숫자에 대한 strike와 boll을 확인
for (int m = 0; m < 3; m++) {
for (int a = 0; a < 3; a++) {
if (check[m] == checkList[a]) {
if (m == a) checkStrike++;
if (m != a) checkBall++;
}
}
}
//srike와 boll이 같지 않은 숫자는 경우의 수에서 삭제 (false)
if (arr[i].strike != checkStrike || arr[i].ball != checkBall)
checkIn[k] = 0;
//다음의 k번째 수를 체크하기위해 다시 0으로 초기화 해놓는다.
checkStrike = 0;
checkBall = 0;
}
//한 n번째 질문에 대하여 123~987 까지의 숫자를 비교해본 결과
}
//n개 질문 모두에 대하여 숫자를 대입하여 check(bool)로 상태를 체크한 결과
//같은 숫자가 한번 더 들어갔거나 0이 들어간 숫자를 모두 제외시킴
for (int i = 123; i < 987; i++)
{
string tmp = to_string(i);
if (tmp[0] == tmp[1] || tmp[0] == tmp[2] || tmp[1] == tmp[2])
checkIn[i] = 0;
if (tmp[0] - '0' == 0 || tmp[1] - '0' == 0 || tmp[2] - '0' == 0)
checkIn[i] = 0;
}
//true인 경우의 수를 체크
int Answer = 0;
for (int i = 123; i <= 987; i++)
{
if (checkIn[i] == 1) Answer++;
}
printf("%d", Answer);
return 0;
}
최대 9명의 키에 대한 입력이 주어지며 주어지는 키가 100이 넘지 않기 때문에 완전 탐색을 통해 문제를 해결하였다.
일곱 난쟁이의 키의 합이 100이 되도록 주어진 9명의 키중에서 2명의 키를 제외하고 7명의 키의 합이 100인 경우를 찾으면 된다.
모든 입력 값의 합을 구한 후 2 명의 키만큼씩을 빼보면서 확인하였으며 2 명의 키를 제외하고 합이 100이 되는 경우 그 값을 제외하여 출력한다.
조건에 따르면 일곱 난쟁이를 찾을 수 없는 경우는 없으며 가능한 정답이 여러 가지인 경우에는 아무거나 출력할 수 있기 때문에 최초로 합이 100이 되는 경우 함수를 return하여 이후의 과정을 생략하도록 하였다.
코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> height;
void solution() {
int sum=0;
//9명의 키의 합을 sum에 미리 저장
for (int i = 0; i < 9; i++)
sum += height[i];
//두명의 키를 제외한 결과가 100인 경우 return
for (int i = 0; i < 9; i++) {
for (int j = i+1; j < 9; j++){
if (sum - (height[i] + height[j]) == 100) {
height.erase(height.begin()+i);
height.erase(height.begin()+j-1);
//i가 이미 erase 된 상태이므로 (j-1) 번째 값을 삭제한다.
return ;
}
}
}
}
int main() {
int tmp;
for (int i = 0; i < 9; i++) {
cin>>tmp;
height.push_back(tmp);
}
solution();
//일곱 난쟁이의 키를 오름차순으로 출력
sort(height.begin(), height.end());
for (int i = 0; i < height.size(); i++)
printf("%d\n", height[i]);
return 0;
}
