[BOJ] 백준 2503 숫자 야구 / 완전 탐색(Brute-force Search)

💣 문제 이해 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오. 문제에 제시된 다음과 같은 조건들을 정리하면 다음과 같다. 1. 영수와 민혁이가 생각한 수는 세 자리 수이고, 각 자리 수는..

→2020.02.24

[BOJ] 백준 3085 사탕 게임 / 완전 탐색(Brute-force Search)

* 예외 처리를 잘하자 💣 문제 이해 1. 행으로 인접한 두 칸을 고르고 교환한다(swap) 2. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다. 3. 열로 인접한 두 칸을 고르고 교환한다(swap) 4. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다. 보통 컴퓨터가 1초에 약 1억번의 연산을 한다. 이 문제에서 배열의 최대 크기라고 해봐야 50*50 이므로 단순하게 모든 경우를 하나하나 따져보아도 50*50*(50*50+50*50) = 12,500,000 이므로 완전 탐색(Brute-force Search) 방식을 사용하기로 했다. 💭 풀이 과정 작성 언어: C++ #include #include using namespace std; int num = 0; char arr[60][60] = ..

→2020.02.19

[BOJ] 백준 1011 Fly me to the Alpha Centauri

* 변수 오버플로우를 잘 고려하자!!! 💣 문제 이해 약간의 수학적인 규칙을 찾는 것이 필요한 문제였다. 첫 번째는 무조건 1 만큼 이동, 이후로는 다음과 같은 규칙이 있다. 이전에 1 만큼 움직였다면 이번에는 0, 1, 2 중 선택해서 이동이 가능하다. 이전에 2 만큼 움직였다면 이번에는 1, 2, 3 중 선택해서 이동이 가능하다. 거리를 입력받았을 때, 이 규칙 내에서 처음 지점에서 끝 지점까지 정확하게 도착할 수 있는 최소 이동 횟수를 구하여 출력하면 된다. 💭 풀이 과정 이동거리를 1부터 차례대로 적어가며 규칙을 찾아보았다. 이동 거리 이동 방식 이동 횟수 1 1 1 2 1 1 2 3 1 1 1 3 4 1 2 1 3 5 1 2 1 1 4 6 1 2 2 1 4 7 1 2 2 1 1 5 8 1 2 2..

→2020.01.07

[BOJ] 백준 2869 달팽이는 올라가고 싶다

* 문제 난이도가 어려운 것은 아니지만, 시간복잡도 계산의 중요성을 새삼 느끼게 한 문제라 기록한다. 💣 문제 이해 문제에 나와있는 것처럼 달팽이는 낮에는 up만큼 올라가고 밤에는 down만큼 미끄러진다. 그러나, 정상에 올라간 후에는 미끄러지지 않는다. 즉, 낮에 up만큼 올라간 후에 나무높이 tree를 넘는다면 down만큼 차감하지 않아도 된다는 것이다. 그런데 간과하면 안 되는 것이 있다. 입력이 최대 10억까지 가능하다는 것, 그리고 시간제한이 0.15초라는 것... 💭 풀이 과정 처음에 작성한 소스이다. (시간 초과) 작성 언어: C++ #include int main(){ int up, down, plus = 0, tree, day = 0; scanf("%d %d %d", &up, &down,..

→2020.01.03

[BOJ] 백준 2447 별 찍기 - 10

재귀함수를 정의해 봅시다. 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. Input 27 Output My Solution #include using namespace std; char arr[7000][7000] = {0,}; void inpStar(int n, int x, int y){ if(n == 1){ arr[x][y] = '*'; return; } int val = n/3; for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ if(i == 1 && j == 1) ..

→2019.10.11

[BOJ] 백준 10872 팩토리얼

재귀함수를 정의해 봅시다. 문제 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N(0 ≤ N ≤ 12)가 주어진다. 출력 첫째 줄에 N!을 출력한다. Input 10 Output 3628800 My Solution #include using namespace std; int main(void){ int input = 0, result = 1; cin >> input; for(int i = 1; i

→2019.10.05

[BOJ] 백준 1065 한수

X가 한수인지 판별하는 함수를 정의하여 문제를 해결해 봅시다. 문제 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. Input 1 110 Output 1 99 Input 2 1 Output 2 1 Input 3 210 Output 3 105 Input 4 1000 Output 4 144 My Solution #include using namespace std; i..

→2019.10.05

[BOJ] 백준 15596 정수 N개의 합

함수를 구현해 봅시다. (이 문제는 C, C++, Python, Java, Go만 지원합니다. 그 외의 언어를 사용하신다면 이 문제를 무시해 주세요.) 문제 정수 n개가 주어졌을 때, n개의 합을 구하는 함수를 작성하시오. 작성해야 하는 함수는 다음과 같다. - C, C11, C (Clang), C11 (Clang): long long sum(int *a, int n); - a: 합을 구해야 하는 정수 n개가 저장되어 있는 배열 (0 ≤ a[i] ≤ 1,000,000, 1 ≤ n ≤ 3,000,000) - n: 합을 구해야 하는 정수의 개수 - 리턴값: a에 포함되어 있는 정수 n개의 합 - C++, C++11, C++14, C++17, C++ (Clang), C++11 (Clang), C++14 (Cl..

→2019.10.05

[BOJ] 백준 4673 셀프 넘버

함수 d를 정의하여 문제를 해결해 봅시다. 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129..

→2019.10.05

[BOJ] 백준 8958 OX퀴즈

OX 퀴즈의 결과를 일차원 배열로 입력받아 점수를 계산하는 문제 문제 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다. "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다. OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다. 출력 각 테스트 케이스마다 점수를 출력한다. Input 5 OOXXOX..

→2019.10.05