알고리즘 스터디 45일차

1. N으로 표현하기

1) 문제

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

입출력 예
N number return
5 12 4
2 11 3

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

int solution(int N, int number) 
{
    int answer = 0;
    if (number == N) return 1;

    vector<unordered_set<int>> vecofset(9);
    vecofset[1].insert(N);

    for (int i=2; i<9; i++)
    {
        int seqN=0;
        // NNN 형태
        for (int j=0; j<i; j++)
        {
            seqN = seqN*10 + N; 
        }

        vecofset[i].insert(seqN);
  		// i개 사용해서 만들 수 있는 수는, i개 , j-1개들의 사칙연산으로 만들 수 있다. 
        for (int j=1; j<i; j++)
        {
            for(auto e1 : vecofset[j])
            {
                for (auto e2 : vecofset[i-j])
                {
                    vecofset[i].insert(e1 + e2);
                    vecofset[i].insert(e1 - e2);
                    vecofset[i].insert(e1 * e2);
                    if (e2 != 0)
                        vecofset[i].insert(e1 / e2);
                }
            }
        }
        if (vecofset[i].count(number)) return i;
    }

    return -1 ;
}

2. 등굣길

1) 문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예
m n puddles return
4 3 [[2, 2]] 4

2) 문제 분석 및 풀이

1) 설계, 분석

2) 풀이

#include <string>
#include <vector>
using namespace std;

#define MOD 1'000'000'007

int solution(int m, int n, vector<vector<int>> puddles) 
{
    int answer = 0;
    vector<vector<int>> land(m+1,vector<int>(n+1, 1));
    vector<vector<int>> dp(m+1,vector<int>(n+1, 0));

    for (int i=0; i < puddles.size(); i++)
    {
        if (puddles[i].size() == 0) continue;
        int x = puddles[i][0];
        int y = puddles[i][1];
        land[x][y] = 0;
    }

    for (int i=1; i<=m; i++)
    {
        if (land[i][1] == 0) break;
        dp[i][1] = 1;
    }

    for (int i=1; i<=n; i++)
    {
        if (land[1][i] == 0) break;
        dp[1][i] = 1;
    }

    for (int i=2; i<=m;i++)
    {
        for (int j=2; j<=n; j++)
        {
            if (land[i][j] != 0)
            {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }
    }

    return dp[m][n];
}