티끌 모아 태산

문제 링크

• 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;
}

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string tmp= "";
    //sill_trees 내의 string 내에 skill string과 동일한 skill만을 저장하기 위한 변수
    for(int i=0;i<skill_trees.size();i++)
    {
        for(int j=0;j<skill_trees[i].size();j++)
        {
            for(int k=0;k<skill.size();k++)
            {
                if(skill_trees[i].at(j)==skill.at(k))
                    tmp.push_back(skill_trees[i].at(j));
                //선행 스킬 순서에 포함된 스킬만 tmp에 저장한다.
            }    
        } 
        if(skill.find(tmp)==0) 
            //find를 실행하였을 때 선행 스킬순서의 첫번째 인덱스를 반환할 때만 
            //사용가능한 유저스킬트리
             answer++;   
        
        tmp=""; 
        //다음 인덱스에서의 확인을 위해 tmp  초기화
     }
    return answer;
}

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    int j=heights.size()-2;
    //heights 벡터의 가장 오른쪽 부터 기록을 진행
    for(int i=j+1;i>=0;i--)
    {   
        //송신탑의 높이가 더 높은 경우 신호가 닿음
        //answer에 push_back하여 신호가 닿은 송신탑 위치 저장
        if(heights[i]<heights[j]){
            answer.push_back(j+1);
            j=i-1;
        }
        //현재 송신탑의 위치에서 끝까지 신호가 닿지 않거나
        //더이상 송신탑이 존재하지 않았을 때는 0 을 push_back
        else if(j==0||i==0)
        {
            answer.push_back(0);
            j=i-1;
        }
        //송신탑이 닿지 않은 경우 현재 송신탑에 대한 탐색
        //j++를 통해 그 다음 송신탑과 통신 확인
        else
        {
            j--;
            i++;
        }
    }
    //answer에 반대의 순서로 push_back해주었기 때문에 reverse
    reverse(answer.begin(),answer.end());
    return answer;
}