1. 데이터를 입력 받는다. N을 먼저 입력 받고, M을 그 다음에 입력 받는다. 2. 기준이 되는 8 * 9 사이즈 체스판 배열을 만들어 아래와 같이 초기화한다. WBWBWBWB - WB 판일 때의 비교 시작 BWBWBWBW - BW 판일 때의 비교 시작 WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB
3. 입력받은 데이터와 체스판을 !=으로 비교연산 하여 그 합계와 현재 값을 비교한다. 4. 3을 통해 구한 가장 적은 합계를 출력한다. ※ 다른 테스트 케이스는 다 맞는데 11 8, 8 11이 틀린다면 반복문을 돌리는 기준이 잘못됐을 가능성이 높다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1018()
{
/*----------기준 체스판----------*/
char standard[9][8];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 8; j++)
{ // i + j가 짝수면 흰색, 홀수면 검정색
standard[i][j] = (i + j) % 2 ? 'B' : 'W';
}
}
/*----------데이터 입력----------*/
int N;
int M;
cin >> N >> M;
char** data = new char*[N];
for (int i = 0; i < N; i++)
{
data[i] = new char[M + 1];
cin >> data[i];
}
/*----------비교 시작----------*/
int changePt = 64;
for (int i = 0; i <= N - 8 && changePt; i++)
{// 비교 시작 위치 지정, changePt == 0인 경우 반복문 종료
for (int j = 0; j <= M - 8 && changePt; j++)
{
int valueWB = 0;
int valueBW = 0;
for (int m = 0; m < 8; m++)
{// 비교 진행
for (int n = 0; n < 8; n++)
{
valueWB += standard[m][n] != data[i + m][j + n];
valueBW += standard[m + 1][n] != data[i + m][j + n];
}
}
changePt = changePt > valueWB ? valueWB : changePt;
changePt = changePt > valueBW ? valueBW : changePt;
}
}
cout << changePt << endl;
/*----------메모리 해제----------*/
for (int i = 0; i < N; i++)
{
delete[] data[i];
}
delete[] data;
return;
}
몸무게와 키로 이루어진 덩치값이 주어졌을 때 A가 B보다 몸무게, 키 값이 모두 크면 A는 B보다 덩치가 크다고 한다. 알 수 없을 때는 동일한 덩치라고 한다. 자신보다 덩치가 큰 사람보다는 등수가 낮지만, 자신과 동일한 덩치끼리는 등수가 같다. 덩치값 배열이 주어졌을 때 각자의 등수를 입력된 순서대로 출력한다.
테스트 케이스
5 55 185 58 183 88 186 60 175 46 155
2 2 1 2 5
2 10 10 10 10
1 1
5 10 10 20 20 30 30 40 40 50 50
5 4 3 2 1
5 50 50 40 40 30 30 20 20 10 10
1 2 3 4 5
5 10 50 20 40 30 30 40 20 50 10
1 1 1 1 1
문제 풀이
각 인원에 대해 배열을 할 때 몸무게, 키와 더불어 N으로 초기화 되는 랭킹 변수를 선언한다. 이후 각 인원간에 비교를 진행하면서 A.weight > B.weight && A.height > B.height 처럼 명확한 경우에는 우위가 있는 쪽의 랭킹 값을 1 낮추고, 우위를 가릴 수 없는 경우에는 양쪽 모두의 랭킹값을 낮춘다. 조정이 모두 완료되면 입력된 순서대로 랭킹 값을 출력해준다.
풀이 코드
#include <iostream>
using namespace std;
int N;
cin >> N;
/*----------데이터 구성----------*/
// data[0] 몸무게
// data[1] 키
// data[2] 등수
/*-------------------------------*/
int** data = new int*[N];
for (int i = 0; i < N; i++)
{
data[i] = new int[3];
cin >> data[i][0] >> data[i][1];
data[i][2] = N;
}
/*----------덩치값 비교----------*/
for (int i = 0; i < N - 1; i++)
{
for (int j = i + 1; j < N; j++)
{
if (data[i][0] > data[j][0] && data[i][1] > data[j][1])
{// i가 j보다 덩치값이 크면
data[i][2]--;
}
else if (data[i][0] < data[j][0] && data[i][1] < data[j][1])
{// j가 i보다 덩치값이 크면
data[j][2]--;
}
else
{// 덩치값의 우위를 알 수 없으면
data[i][2]--;
data[j][2]--;
}
}
}
/*----------등수 출력하기----------*/
for (int i = 0; i < N; i++)
{
cout << data[i][2];
if (i != N - 1)
{
cout << ' ';
}
}
cout << "\n";
/*----------메모리 해제----------*/
for (int i = 0; i < N; i++)
{
delete[] data[i];
}
delete[] data;
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
최상단 시작 지점에서 가장 아래층까지 내려가면서 거치는 경로 중 값의 합이 가장 큰 값은 몇인가.
목적지가 어디가 될지 알 수 없으므로 목적이 후보에서부터 출발지로 거슬러 올라가는 방식으로 구해야 한다. i + 1의 값과 i의 값을 합하여 합계가 큰 쪽은 남겨두는 방식으로 출발지점까지 거슬러 올라가면 합계가 가장 큰 값을 빠르게 구할 수 있다. 설명으로 나온 숫자 배열을 예로 들면 아래와 같이 진행된다.
이와 같은 방식으로 진행하면 결과 값을 빠르게 얻을 수 있다.
#include <iostream>
#include <fstream>
int Problem018()
{
/*---------------값 입력 받기------------------*/
std::ifstream file("Project_Euler_018.txt");
if (!(file.is_open()))
{
return -1;
}
int numArr[15][15] = { 0 };
for (int i = 0; i < 15; i++)
{
for (int j = 0; j <= i; j++)
{
file >> numArr[i][j];
}
}
file.close();
/*-----------------계산하기--------------------*/
for (int i = 13; i >= 0; i--)
{
for (int j = 0; j <= i; j++)
{
int sumLeft = numArr[i][j] + numArr[i + 1][j];
int sumRight = numArr[i][j] + numArr[i + 1][j + 1];
numArr[i][j] = sumLeft > sumRight ? sumLeft : sumRight;
}
}
return numArr[0][0];
}
분해합은 숫자 i에 i의 각 자리 수를 모두 합한 값을 의미한다. i를 분해합하여 N이 나오는 경우 i는 N의 생성자라 한다. 입력된 수 N의 생성자를 출력한다.
테스트 케이스
1
0
2
1
216
198
999999
999954
1000000
0
문제 풀이
브루트 포스로 푸는 문제지만, 1부터 시작하는건 매우 비효율적이므로 범위를 어느 정도 좁힐 필요가 있다. 생성자 수 + 생성자의 각 숫자를 모두 합해서 N이 나와야 하므로 (N - 자리수 * 9) ~ (N - 1) 이 탐색 범위가 된다. 10 이하인 수는 짝수에게만 생성자가 있으므로 그에 맞춰 코드를 작성하면 된다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_2231()
{
int N;
cin >> N;
int M = 0;
if (N <= 10)
{
M = N % 2 == 0 ? N / 2 : 0;
}
else
{
int digit = 0;
int copyN = N;
while (copyN)
{
digit++;
copyN /= 10;
}
for (int i = N - digit * 9; i < N; i++)
{
int currentNumber = i;
int sum = i;
while (currentNumber)
{
sum += currentNumber % 10;
currentNumber /= 10;
}
if (sum == N)
{
M = i;
break;
}
}
}
cout << M << endl;
return;
}
N개의 수열 내에서 세 개의 수를 조합하였을 때 M을 넘지 않는 근사값은 몇인지 출력한다.
테스트 케이스
5 21 6 7 8 9 10
21
5 21 10 9 8 7 6
21
3 300000 100000 100000 100000
300000
10 10 1 2 1 2 1 2 1 2 1 2
6
문제 풀이
브루트 포스로 푸는 문제다. 모든 조합을 확인하여 M과 근사한 값을 찾아내면 된다. M과 동일한 값인 경우에는 문제의 답이 나온 것이므로 그대로 결과를 출력하고 종료하면 된다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_2798()
{
int N;
int M;
cin >> N >> M;
int card[100];
for (int i = 0; i < N; i++)
{
cin >> card[i];
}
int result = 0;
for (int i = 0; i < N - 2 && result < M; i++)
{
for (int j = i + 1; j < N - 1 && result < M; j++)
{
for (int n = j + 1; n < N && result < M; n++)
{
int sum = card[i] + card[j] + card[n];
if (sum > result && sum <= M)
{
result = sum;
}
}
}
}
cout << result << endl;
return;
}
케이스가 세 가지로 나뉜다. A와 B 사이에 있는 경우, A와 B사이에 있지 않은 경우, A와 B가 같은 경우. 목표가 A와 B 사이에 있는 경우에는 r1 + r2의 절대값을 A - B의 거리와 비교하여 결과를 출력하고 목표가 A와 B 사이에 없는 경우에는 r1 - r2의 절대값을 A - B의 거리와 비교하여 결과를 출력한다. 만약 A와 B의 위치가 같다면 r1와 r2를 비교하는 것만으로 충분하다.
풀이 코드
#include <iostream>
using namespace std;
void BAEKJOON_1002()
{
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int x1;
int y1;
int x2;
int y2;
int r1;
int r2;
cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
int result;
if (x1 == x2 && y1 == y2) // A와 B가 같은 위치인 경우
{
result = r1 == r2 ? -1 : 0;
}
else
{
int distance = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
if (r1 * r1 < distance && r2 * r2 < distance) // A와 B 사이에 있는 경우
{
if ((r1 + r2) * (r1 + r2) > distance)
{
result = 2;
}
else if ((r1 + r2) * (r1 + r2) == distance)
{
result = 1;
}
else
{
result = 0;
}
}
else // A와 B 사이에 없는 경우
{
if ((r1 - r2) * (r1 - r2) < distance)
{
result = 2;
}
else if ((r1 - r2) * (r1 - r2) == distance)
{
result = 1;
}
else
{
result = 0;
}
}
}
cout << result << endl;
}
return;
}
반지름 R이 주어졌을 때 유클리드 기하학에서의 원의 넓이와 택시 기하학에서의 원의 넓이를 출력한다.
테스트 케이스
1
3.141593 2.000000
2
12.566371 8.000000
문제 풀이
설명에 원이라는 표현이 들어가서 혼란이 있을 수 있지만 택시 기하학에서 같은 거리라는 것은 각 변의 길이가 동일한 마름모 모양을 의미한다. #참고링크 따라서 택시 기하학의 넓이는 R * R * 2로 나타낼 수 있다. 유클리드 기하학과 관련하여 소수점 6자리까지 출력되어야 하므로 cout << fixed를 해줘야 한다. 이 문제에서 사용하는 π는 소수점 12자리까지 필요하며 (3.141592653589), cmath 상수인 M_PI를 이용해도 무방하다.
풀이 코드
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
using namespace std;
void BAEKJOON_3053()
{
int R;
cin >> R;
cout << fixed;
cout << R * R * M_PI << endl;
cout << R * R * 2.0 << endl;
return;
}
