개발 블로그

문제 링크 : https://www.acmicpc.net/problem/9251

ACAYKP
CAPCAK

4

---

 

접근 방법

처음에는 완전 탐색으로 해결하려고 했다. 그러나 해당 문제의 제한 시간은 0.1초라 dp로 해결해야함을 알게 되었다.

최장 공통 수열을 찾기 위해서는 마지막의 문자에 주목해야한다. 

ABDE와 ABE의 공통 수열을 찾는다고 해보자. 주어진 문자열은 길이가 짧아서 바로 LCS = "ABE"라는 답이 나오지만, 

문자열이 길어지면 한 눈에 파악하기 어렵다. 그럴 때는 마지막부터 거꾸로 거슬러 올라갈 수 있다.

즉, 마지막 문자열인 E가 동일하니, ABD와 AB의 LCS에 +1을 더하면 그것이 답이 되는 것이다. (arr[i-1][j-1] + 1)

그러나 이 로직은 마지막 문자가 서로 같을 경우에만 적용되며, ABD와 AB처럼 서로 다른 경우에는 아래와 같이 경우를 나눠서 생각해야 한다.

1)  D를 포함시킬 때 : ABD - A 간의 LCS = 1(A)    (arr[i-1][j])

2) B를 포함시킬 때 : AB - AB 간의 LCS = 2(AB)  (arr[i][j-1])
서로 다른 끝 문자를 하나씩 포함시킬 때, 둘 중 LCS의 최대값이 ABD와 AB의 LCS가 된다. Max(arr[i-1][j], arr[i-1][j])

 

이를 코드로 작성하면 아래와 같다. 

 

import java.util.*;
public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String strA = sc.nextLine();
        String strB = sc.nextLine();

        int arr[][] = new int[1001][1001];

        for(int i = 1; i<=strB.length(); i++){
            for(int j = 1; j<=strA.length(); j++){
                if(strB.charAt(i-1) == strA.charAt(j-1)){	//끝 문자가 같을 때 
                    //arr[i][j] = arr[i-1][j] + 1;
                    arr[i][j] = arr[i-1][j-1] + 1;
                }
                else{										//끝 문자가 다를 때
                    //arr[i][j] = arr[i][j-1];
                    arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j]);	
                }
            }

        }
        System.out.println(arr[strB.length()][strA.length()]);
    }
}

 

문제 링크 : https://www.acmicpc.net/problem/13164

접근 방법

먼저 같은 조에 속한 원생들은 서로 인접해야 하는 것에 주의하자. 

하기의 입력 예시로 생각해보자. 

5 3
1 3 5 6 10

여기서 3개의 조로 원생들을 나누어야 하는데, 같은 조 원생들은 서로 인접해야 하기 때문에

주어진 1 3 5 6 10 에서 2개의 막대기를 원생들 사이에 두면 조건을 만족하면서 조를 나눌 수 있다. 예시는 아래와 같다. 

1 |  3  5  |  6  10   => 비용 : 2 + 4 = 6

1  3  |  5  | 6  10   => 비용 : 2 + 4 = 6

1  3  |  5  6  |  10   => 비용 : 2 + 1 = 3 (최저 비용)

그렇다면 막대기 K-1개는 어디에 두어야할까? 바로 인접한 원생과의 키차이가 가장 크게 나는 곳에 두어야 한다. 키차이가 가장 크게 나는 곳에 막대기를 두게 되면, 그 키차이(비용)은 제외되어 버리기 때문이다.

위 예시에서 생각해보면 

1 3 5 6 10 일 때, 원생들과의 키차이는 

2 2 1 4 이기 때문에

키차이가 2와 4인 곳에 막대기를 두어야 하는 것이다. 그럼 비용에서 2, 4는 제외되고 2, 1만 남는다. (2+1이 최소 비용)

일반화를 해보면 다음과 같다.

1) 인접한 원생들 사이의 키차이를 구한다. 

2) 키차이를 내림차순으로 정렬한다. (위 예시에서는 4 2 2 1)

3) 막대기 K-1개로 조를 나눈다. 즉 내림차순으로 정렬된 수열에서 K-1개를 제외한다.

4) 제외하고 남은 키차이들을 다 더하면 그 합이 티셔츠의 최소 비용이 된다. 

import java.io.IOException;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class BOJ_13164_행복유치원 {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        int answer = 0;
        ArrayList<Integer> tall = new ArrayList<>();
        ArrayList<Integer> subTall = new ArrayList<>();
        
        //키 입력받기
        for(int i = 0; i<N; i++){
            tall.add(sc.nextInt()); 
        }
        //키 차이 구하기
        for(int i = 0; i < N-1; i++){
            subTall.add(tall.get(i+1) - tall.get(i));
        }
        //키 차이 오름차순 정렬
        Collections.sort(subTall);

        //가장 큰 키차이를 K-1개 제외하고 나머지들 더함
        for(int i = 0; i < N-K; i++){
            answer += subTall.get(i);
        }
        System.out.println(answer);
    }
}

문제 : https://www.acmicpc.net/problem/1669

접근 방법

이 문제는 규칙을 잘 찾아야하는 문제이다. 문제에서 주어진 조건을 봐보면 키를 1cm 차이가 나게 조절을 해야하는데, 이 때 첫째 날과 마지막 날은 무조건 1cm가 되어야 한다. 이 점을 유의깊게 봐보자.

우리는 최소의 일수를 구해야 하기 때문에 첫째 날 키 조절 양을 1cm 로 시작을 해서 2, 3, 4,,, 로 키를 키워나가야 하지만

마지막 날의 키 조절 양도 1cm로 끝나야하기 때문에

어느 정도 고점 x에 도달한 뒤에는 x-1, x-2, x-3,,, 1 과 같이 키의 양을 줄여나갸야 하는 것이다. 

그렇다면  그 고점을 어떻게 찾아야할까? 

규칙이 보이지 않을 때에는 먼저 나열을 쭉 해보고 그 안에서 규칙을 찾아보는것도 좋은 방법이다. 

키 차이 (Y-X) 를 sub이라고 하자. 멍멍이와 원숭이의 키가 같아지기 위한 최소 일수를 찾아보자. 

   * 괄호 안의 수는 각 날에 조절한 키의 양이다.)

sub = 1 일 때 : 1일 (1)

sub = 2일 때 : 2일 (1, 1)

sub = 3일 때 : 3일 (1, 1, 1)

sub = 4일 때 : 3일 (1, 2, 1)

sub = 5일 때 : 4일 (1, 2, 1, 1)

sub = 6일 때 : 4일 (1, 2, 2, 1)

sub = 7일 때 : 5일 (1, 2, 2, 1, 1)

sub = 8일 때 : 5일 (1, 2, 2, 2, 1)

sub = 9일 때 : 5일 (1, 2, 3, 2, 1)

sub = 10일 때 : 6일 (1, 2, 3, 2, 1, 1)

sub = 11일 때 : 6일 (1, 2, 3, 2, 2, 1)

sub = 12일 때 : 6일 (1, 2, 3, 3, 2, 1)

sub = 13일 때 : 7일 (1, 2, 3, 3, 2, 1, 1)

sub = 14일 때 : 7일 (1, 2, 3, 3, 2, 2, 1)

sub = 15일 때 : 7일 (1, 2, 3, 3, 3, 2, 1)

sub = 16일 때 : 7일 (1, 2, 3, 4, 3, 2, 1)

sub = 17일 때 : 8일 (1, 2, 3, 4, 3, 2, 1, 1)

제곱수를 보면 sub = N^2 라고 했을 때 고점이 N 인것을 확인할 수 있고, 필요한 최소 일수는 N^2 - 1 인 것을 확인할 수 있다. 
그렇다면 제곱수가 아닌 수는 어떤 규칙이 있을까?

예를 들어 sub = 13일 때를 보자. 13보다 작은 제곱수인 9(1, 2, 3, 2, 1) 을 제외하면 (1, 2, 3, 3, 2, 1, 1) 중 (3, 1)이 남는데

이는 루트 9보다 작은 수 중 적당히 끼워 넣은 것이다. 

즉,

1) 키 차이보다 작은 최대 제곱수 N^2 를 찾고

2) 키 차이에서 최대 제곱수를 뺀 나머지를 구한 다음

3) 나머지가 N이하의 수들로 어떻게 구성되어있는지 찾으면 되는 것이다. (문제에서 최소 일수를 찾는 것이 목표이기 때문에 이때 가장 큰 수인 N부터 검사하도록 한다. )

이를 코드로 나타내면 아래와 같다.

*주의 ) N과 ans를 long형으로 선언해야한다. (오버플로우 방지 (?) )

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int y = sc.nextInt();
        int sub = y - x;
        
        if(sub == 0){				// 예외처리 : 처음부터 키가 같을 때
            System.out.println(0);
            return;
        }

        long N = 1;				//long 형으로 선언해야한다.
        long ans = 0;

        while(N*N <= sub){ 			//키차이보다 작은 최대 제곱수를 찾는다.
            N++;
        }
        N-=1;					//N++된 상태로 while문을 빠져나오기 때문에 -1 해준다.
        ans = 2*N - 1;				//answer 초기 값 설정 

        sub -= N*N;				//제곱수만큼 빼고 남은 키로 while 문을 돈다.
        while(sub > 0){

            for(long i = N; 1<=i; i--){		//N부터 시작해서
                if(i<=sub){					//i가 sub보다 작으면 
                    ans+=1;
                    sub -= i;				//sub에서 i를 뺀다.
                    break;
                }
                else continue;				
            }
        }
        System.out.println(ans);
    }

}

문제 : https://www.acmicpc.net/problem/1662

접근 방법

[처음 코드]

입력 문자열을 stack 에 push 한 뒤, 단순하게 문자열 끝(stack의 top)부터 탐색을 진행했다. 탐색을 진행할 때는 세가지 케이스를 나눴다. 먼저 그냥 숫자이면 len을 하나씩 증가시키고, ')'이면 pop 하고, '('이면 '('의 앞 숫자(k)를 len에 곱했다. 

그러나 아래 코드는 문제에서 주어진 예제는 맞췄으나, 또 다른 반례를 생각하지 못했다. 

반레 : () 안에 압축 문자열이 여러개가 포함이 될 때  -> ex. 45(12)53(52(1111)42(222)) 

import java.util.*;
public class Main {

    public static void main(String[] args) {

        String input;
        Scanner sc = new Scanner(System.in);
        input = sc.next();
        int inputLen = input.length();

        char[] arr = input.toCharArray();

        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < inputLen; i++){
            stack.push(arr[i]);
        }

        int len = 0;
        while(!stack.empty()){
            char topChar = stack.peek();
            if(topChar == ')') {
                stack.pop();
            }
            else if(topChar == '('){
                stack.pop();
                int k = (int)stack.pop() - '0';
                len = len*k;
              
            }
            else{
                len++;
                stack.pop();
            }
        }
        System.out.println(len);
    }
}

[정답 코드]

입력 문자열을 끝이 아닌 처음부터 stack에 push 해가면서 탐색을 진행한다. 단 ')'를 만나기 전까지 탐색을 진행한다. ')'를 만나면 push 했던 문자열들을 pop 해가면서 압축 문자열을 해제하는 로직을 수행한다. 이 때 while문을 돌면서 '('를 만나기 전까지 stack에서 pop해가면서 길이를 계산한다. K(Q)의 길이를 알아냈다면, 그 길이를 다시 stack에 push하는데, 이는 하나의 괄호 쌍 안에 여러개의 압축 문자열이 있을 때를 위한 것이며, 계산한 압축 문자열의 길이와 기존에 입력 문자열을 구분하기 위해 계산한 압축 문자열의 길이를 push 할 때에는 길이를 push한 뒤에 바로 "+"를 push 해준다. 

입력 문자열의 끝까지 push하면서 탐색을 끝냈다면, stack에서 하나씩 Pop 해가면서 최종 길이를 계산한다.

*주의 :  Stack Type을 Char형으로 정의 시 형변환 하는 과정에서 오류 -> String Type으로 정의해야한다.

import java.util.*;
import java.io.*;
public class BOJ1662_압축 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");

        Stack<String> stack = new Stack<String>();
        for(int i = 0; i < arr.length; i++){

            if(!arr[i].equals(")")) {stack.push(arr[i]);}
            else {
                int cnt = 0;
                while (!stack.peek().equals("(")) {
                    String topStr = stack.pop();
                    if (topStr.equals("+")) {
                        int len = Integer.parseInt(stack.pop());
                        cnt += len;
                    } else cnt++;
                }
                stack.pop(); // ( 제거
                int k = Integer.parseInt(stack.pop());
                cnt = cnt * k;
                stack.push(String.valueOf(cnt));
                stack.push("+");
            }
     }
        int answer = 0;
        while(!stack.empty()){
            if(stack.peek().equals("+")){
                stack.pop();
                //System.out.println(stack.peek());
                answer += Integer.parseInt(stack.pop());
            }
            else{
                stack.pop();
                answer++;
            }
        }
        System.out.println(answer);
    }
}

참고 : https://codeung.tistory.com/256

문제 링크 : https://www.acmicpc.net/problem/2042

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

접근 방법

데이터가 최근에 추가된 것 같은데, 문제에 주어진 조건이 명확하지 않아서 정답까지 오래 걸린 문제였다. N의 최대 값은 int 형인데 b,c모두 N을 넘지 않으므로 int형으로 선언했는데 계속 틀렸습니다가 출력됐다. 

100%에서 틀리는 경우에는 a,b,c모두 long long 으로 선언해서 다시 시도해보도록 하자! (c만 long long 으로 선언해줘도 되는데 문제에서 입력값 모두 long long형이라고 했으므로, 입력 값은 맘 편하게 모두 long long으로 선언하도록 하자.)

참고 : https://www.acmicpc.net/board/view/62196

#define MAX 1000001
#include <iostream>
using namespace std;

int N, M, K;
long long arr[MAX];

long long segTree[4000004];

long long init(int start, int end, int nodeNum)
{ //start : 시작 인덱스, end : 끝 인덱스,
    if (start == end)
        return segTree[nodeNum] = arr[start]; //리프 노드

    int mid = (start + end) / 2;
    return segTree[nodeNum] = init(start, mid, nodeNum * 2) + init(mid + 1, end, nodeNum * 2 + 1);
}

//start, end : 해당 노드의 시작, 끝 인덱스
//left, right : 구간 합 구하고자 하는 범위
long long subSum(int start, int end, int nodeNum, int left, int right)
{
    if (left > end || right < start)
        return 0;

    if (left <= start && end <= right)
        return segTree[nodeNum]; //완전히 포함 (6~11 구하고 싶은데 해당 노드가 6~8일 때)
    int mid = (start + end) / 2;
    return subSum(start, mid, nodeNum * 2, left, right) + subSum(mid + 1, end, nodeNum * 2 + 1, left, right);
}

void update(int start, int end, int nodeNum, int targetIdx, long long val)
{
    if (targetIdx < start || end < targetIdx)
        return;

    segTree[nodeNum] += val;
    if (start == end)
        return;
    int mid = (start + end) / 2;
    update(start, mid, nodeNum * 2, targetIdx, val);
    update(mid + 1, end, nodeNum * 2 + 1, targetIdx, val);
}

int main()
{

    cin >> N >> M >> K;

    int num;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    //1. 세그먼트트리 만들기 (트리 인덱스는 1부터 ~ )
    init(0, N - 1, 1);

    long long a, b, c;
    for (int i = 0; i < M + K; i++)
    {
        cin >> a >> b >> c;
        if (a == 1)
        { //b번째 인덱스를 c로 바꾸기. 바뀐 차이 만큼 트리 각 노드에 더해줘야함.
            long long tmp = c - arr[b - 1];	//arr 값 바꾸기 전에 값 저장해놓아야 파라미터로 넘길 수 있음
            arr[b - 1] = c;
            update(0, N - 1, 1, b - 1, tmp);
        }
        else
        { //b~c 합(b=3, c = 7이면 arr[2]~arr[6] 구해야 함)
            cout << subSum(0, N - 1, 1, b - 1, c - 1) << "\n";
        }
    }

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/2748

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

접근 방법

처음에는 재귀 함수로 풀었는데 시간 초과가 났다.

그래서 DP로 풀었는데 dp[]의 자료형을 int 형으로 지정해서 오답으로 처리됐다. F(90) = 2,880,067,194,370,816,120 이므로 dp[]는  long long 형으로 선언해줘야한다. 

F(45) = 1836311903
F(46) = 2971215073
이므로 n = 46부터 int형 범위를 넘어간다. 

* long long(8byte) : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 
* long (4byte) : –2,147,483,648 ~ 2,147,483,647

의문) long형으로 선언해도 백준은 정답으로 처리돼서 테스트케이스에 n=90이 없나 싶었는데,

         VsCode에서도 F(90)이 정상적으로 출력된다. 이론상으로는 long long 이 맞는데 정답 처리 되는 이유를 잘 모르겠다.

#include <iostream>
using namespace std;

long long dp[91]={0,};

int main()
{
    int n; cin >> n;
    
    dp[0] = 0; dp[1] = 1;
    for(int i = 2; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n];
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/17069

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

세로

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

입력

첫째 줄에 집의 크기 N(3 ≤ N ≤ 32)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

출력

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다.

접근 방법

파이프 옮기기1번(https://nanyoungkim.tistory.com/183)

과 문제는 같지만, N 최대값이 16에서 32로 커졌기 때문에 같은 코드로는 시간초과가 났다.

- DP와 삼차원 배열을 이용해서 해결해보자. 

- dp[i][r][c] : 파이프 방향이 i이고, 현재 파이프 끝의 위치가 [r][c]일때의 (1,2)부터 (r,c) 로 가는 방법의 수

step 1) 처음 시작 위치 초기화

dp[0][1][2] : 처음 초기 상태로 1을 저장한다.

step 2) 첫 줄 초기화

dp[0][1][3]부터 dp[0][1][N]은 (1,2)에서 시작해서 가로로 쭉 이동하는 경우밖에 없다. 쭉 이동하면서 1로 초기화 하되, 벽이 나타나면 가로로 더 이상 이동할 수 없으므로 중단한다. (벽 오른쪽은 모두 0 인 상태로 남게 됨)

stpe 3) dp 채우기

첫번째 줄은 채웠으니, 두번째 줄과 두번째 열부터 dp를 채운다.

이때 경우는 아래의 3가지로 나눌 수 있다. 

(이전위치) -> (현재 위치 & 현재 상태 가로일 때) : 현재(r,c) 상태가 가로이므로 이전 위치는 (r, c-1)이며, 이전 상태는 가로/대각선.

(이전위치) -> (현재 위치 & 현재 상태 세로일 때) : 현재(r,c) 상태가 세로이므로 이전 위치는 (r-1, c)이며, 이전 상태는 세로/대각선.

(이전위치) -> (현재 위치 & 현재 상태 대각선일 때): 현재(r,c) 상태가 대각선이므로 이전 위치는 (r-1,c-1)이며, 이전 상태는 가로/세로/대각선

이 세 경우를 코드로 표현하면 아래와 같다. 세번째 경우는 대각선으로 이동한 경우이므로 (r,c)의 위와 왼쪽도 벽이 아닌지 검사해야한다.

for (int r = 2; r <= N; r++)
    {
        for (int c = 2; c <= N; c++)
        {
            if (map[r][c] == 1)
                continue;

            //가로 -> 가로  , 대각선 -> 가로  : (r,c-1) -> (r,c)
            dp[0][r][c] = dp[0][r][c - 1] + dp[2][r][c - 1];

            //세로 -> 세로   , 대각선 -> 세로  : (r-1, c) -> (r,c)
            dp[1][r][c] = dp[1][r - 1][c] + dp[2][r - 1][c];

            //가로 -> 대각선, 세로 -> 대각선  , 대각선 ->대각선  : (r-1, c-0) -> (r,c)
            if (map[r - 1][c] != 1 && map[r][c - 1] != 1)
                dp[2][r][c] = dp[0][r - 1][c - 1] + dp[1][r - 1][c - 1] + dp[2][r - 1][c - 1];
        }
    }

전체 코드 

//
//  BF_BOJ17070_파이프옮기기2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/08/12.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
using namespace std;

int N;
int map[33][33];
long dp[3][33][33];

int main()
{

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> map[i][j];
        }
    }

    for (int col = 2; col <= N; col++)
    { //(1,2) 에서 오른쪽으로 가로로 쭉 이동
        if (map[1][col] == 1)
            break;
        else
            dp[0][1][col] = 1;
    }

    for (int r = 2; r <= N; r++)
    {
        for (int c = 2; c <= N; c++)
        {
            if (map[r][c] == 1)
                continue;

            //가로 -> 가로  , 대각선 -> 가로  : (r,c-1) -> (r,c)
            dp[0][r][c] = dp[0][r][c - 1] + dp[2][r][c - 1];

            //세로 -> 세로   , 대각선 -> 세로  : (r-1, c) -> (r,c)
            dp[1][r][c] = dp[1][r - 1][c] + dp[2][r - 1][c];

            //가로 -> 대각선, 세로 -> 대각선  , 대각선 ->대각선  : (r-1, c-0) -> (r,c)
            if (map[r - 1][c] != 1 && map[r][c - 1] != 1)
                dp[2][r][c] = dp[0][r - 1][c - 1] + dp[1][r - 1][c - 1] + dp[2][r - 1][c - 1];
        }
    }
    cout << dp[0][N][N] + dp[1][N][N] + dp[2][N][N];

    return 0;
}

참고(https://hbj0209.tistory.com/118)

문제 링크 : https://www.acmicpc.net/problem/10942

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

접근 방법

처음에는 S, E를 입력할 때마다 양쪽에서 가운데 방향으로 대칭을 이루는지 검사했다. 그런데 이 방법은 시간초과가 났다.

시간을 줄이기 위해 효율적인 DP 로 해결해보았다. 다음과 같이 생각해보자.

s = 1, e = 5가 팰린드롬인지 알려면 다음 두가지 조건이 만족하는지 검사해보면 된다.

조건 1) arr[1]과 arr[5]가 같은가?

조건 2) arr[2] 부터 arr[4]가 팰린드롬인가?

즉, dp[s][e] 에 arr[i] ~ arr[i]가 팰린드롬인지를 저장한다고 했을 때,

if((arr[s] == arr[e])  &&  (dp[s+1][e-1] == true)) => dp[s][e] = true 가 된다.

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

using namespace std;
int arr[2001] = {
    0,
};
int dp[2001][2001]; //dp[i][j] : arr[i] ~ arr[j] 가 팰린드롬 문자열인지 여부

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }

    //dp[x][x]와  + 길이가 2인 팰린드롬 dp[i][i+1] 을 셋팅.
    for (int i = 1; i <= N - 1; i++)
    {
        dp[i][i] = 1; //dp[x][x] 는 항상 true 임
        if (arr[i] == arr[i + 1])
            dp[i][i + 1] = 1;
        else
            dp[i][i + 1] = 0;
    }
    dp[N][N] = 1;

    for (int len = 3; len <= N; len++)
    {

        for (int st = 1; st <= N - len + 1; st++)
        {
            //s = st, e = st+len-1
            if ((arr[st] == arr[st + len - 1]) && (dp[st + 1][st + len - 2]))
            {
                dp[st][st + len - 1] = 1;
            }
            else
                dp[st][st + len - 1] = 0;
        }
    }
    int M;
    cin >> M;
    int S, E;

    for (int i = 0; i < M; i++)
    {
        cin >> S >> E;
        cout << dp[S][E] << "\n";
    }

    return 0;
}