[BOJ/백준] 1248 맞춰봐

● [문제번호 1248] 맞춰봐

https://www.acmicpc.net/problem/1248

1248번: 맞춰봐

 

● 알아야 할 것

: DFS

: 재귀

 

● 풀이 과정

: DFS의 기본 구현 형태에서 벗어나지 않지만,

주의하고 확인할 조건들을 잘 구현한다.

 

: -10부터 10까지 순서대로

각 열의 모든 행의 부호 조건에 만족하는 숫자를 찾으면

다음 열로 넘어간다.

 

모든 행 → 부호가 있는 모든 행

 

 

● 주의 할 것

: 부호 확인 방법을 구현할 때 어떤 순서로 구해지는 지 이해해야한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// S : S[i][j] = A[i] + ... + A[j] 의 부호 저장
// A : N개의 숫자 배열 저장
char S[11][11];
int A[11];
int N;

// N개의 숫자 배열 찾기
int number(int cnt)
{
    // 숫자 배열을 찾은 경우
    if(cnt == N)
        return 1;
    
    // -10부터 10까지 순서대로 탐색
    for(int i = -10; i <= 10; i++)
    {
        // 각 행의 부호에 맞는 지 확인 (모두 통과 : 행의 수 / 그 외 : 행의 수보다 작음)
        int flag = 0;
        
        // 모든 행 (대각성분까지) 확인
        for(int row = 0; row <= cnt; row++)
        {
            // S[i][j] 값 구하기 (j-1 까지 구하고 아래 조건문에서 추가함)
            // (not 부호)
            int total = 0;
            for(int t = row; t < cnt; t++)
                total += A[t];
            
            // 부호에 맞는 지 확인
            if(S[row][cnt] == '+' && 0 < total + i)
                flag++;
            else if(S[row][cnt] == '-' && total + i < 0)
                flag++;
            else if(S[row][cnt] == '0' && total + i == 0)
                flag++;
            else
                break;
        }
        
        // 모든 행의 부호에 맞는 경우
        if(flag == cnt + 1)
        {
            // 숫자 저장하고
            // 재귀
            // (숫자 배열 찾은 경우 더이상 진행X)
            A[cnt] = i;
            if(number(cnt + 1))
                return 1;
        }
    }
    return 0;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // S[i][j] 의 부호 저장
    for(int row = 0; row < N; row++)
        for(int col = row; col < N; col++)
            cin >> S[row][col];
    
    // A 배열에 숫자 0개 저장되어 있기에
    number(0);
    
    // A 배열 출력
    for(int i = 0; i < N; i++)
        cout << A[i] << " ";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [530 - 브루트 포스 - 재귀] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/258
2	1759	암호 만들기	https://pirateturtle.tistory.com/259
3	14501	퇴사	https://pirateturtle.tistory.com/260
4	14889	스타트와 링크	https://pirateturtle.tistory.com/261
5	15661	링크와 스타트	https://pirateturtle.tistory.com/262
6	2529	부등호	https://pirateturtle.tistory.com/263
7	1248	맞춰봐	https://pirateturtle.tistory.com/264