24313번 점근적 표기 1 , 2798번 블랙잭, 2231번 분해합, 19532번 수학은 비대면 강의입니다 , 1018번 체스판 다시 칠하기
코딩테스트 : 점근적 표기 1
문제
오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.
입력
첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)
출력
f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.
처음엔 문제가 이해가 잘 안가서 한참 봤다.
그러니까 O(g(n))이라는 함수는 f(n) <= c x g(n)인 함수의 집합이라는 것이다.
즉, f(n)은 g(n)보다 빨리 커지는 속도가 빠를 수 없다.
using System;
using System.Linq;
public class Program
{
public static void Main()
{
int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
int a0 = s[0];
int a1 = s[1];
int c = Int32.Parse(Console.ReadLine());
int n0 = Int32.Parse(Console.ReadLine());
int n = n0;
if (a0 * n + a1 <= c * n)
{
Console.WriteLine(1);
}
else
{
Console.WriteLine(0);
}
}
}일단 예제 통과는 되지만, '커지는 속도'를 구분한 것이 아니기 때문에 따로 또 조건을 달아줘야 한다.
결국 n의 계수가 크고, n0 부분에서도 크다면 식이 성립할 것이다.
반대로 n의 계수가 작다면 ? 상수 c가 아무리 커도 n이 무한대로 간다면 식이 성립하지 않을 것이다.
using System;
using System.Linq;
public class Program
{
public static void Main()
{
int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
int a0 = s[0];
int a1 = s[1];
int c = Int32.Parse(Console.ReadLine());
int n0 = Int32.Parse(Console.ReadLine());
int n = n0;
if (a0 <= c)
{
if (a0 * n + a1 <= c * n)
{
Console.WriteLine(1);
}
else
{
Console.WriteLine(0);
}
}
else
{
Console.WriteLine(0);
}
}
}다른 사람의 흥미로운 풀이
조건을 둘로 나눌 필요 없이, 그냥 한 번에 쓸 수 있다.
코딩테스트 : 2798번 블랙잭
문제
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.
using System;
using System.Linq;
public class Program
{
public static void Main()
{
int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
int n = s[0];
int m = s[1];
int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
int maxNum = int.MinValue;
for (int i = 0; i < n-2; i++)
{
for (int j = i + 1; j < n-1; j++)
{
for (int k = j + 1; k < n; k++)
{
int currentNum = numbers[i];
currentNum += numbers[j];
currentNum += numbers[k];
if (currentNum <= m && currentNum > maxNum)
{
maxNum = currentNum;
}
}
}
}
Console.WriteLine(maxNum);
}
}
처음에 시간이 넘을까... 해서 망설였지만 일단 가장 쉬운 방법으로 했다.
코딩테스트 : 2231번 분해합
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
using System;
using System.Linq;
public class Program
{
public static void Main()
{
int s = int.Parse(Console.ReadLine());
for (int i = 0; i < s; i++)
{
int x = i.ToString().Count();
int[] array = new int[x];
int n = i;
int answer = i;
for (int j = 0; j < x; j++)
{
array[j] = n % 10;
n = n / 10;
}
for (int k = 0; k < x; k++)
{
answer += array[k];
}
if (answer == s)
{
Console.WriteLine(i);
return;
}
}
Console.WriteLine(0);
}
}코딩테스트 : 19532번 수학은 비대면 강의입니다.
문제
수현이는 4차 산업혁명 시대에 살고 있는 중학생이다. 코로나 19로 인해, 수현이는 버추얼 학교로 버추얼 출석해 버추얼 강의를 듣고 있다. 수현이의 버추얼 선생님은 문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다.
{ax+by=cdx+ey=f
4차 산업혁명 시대에 숙제나 하고 앉아있는 것보다 버추얼 친구들을 만나러 가는 게 더 가치있는 일이라고 생각했던 수현이는 이런 연립방정식을 풀 시간이 없었다. 다행히도, 버추얼 강의의 숙제 제출은 인터넷 창의 빈 칸에 수들을 입력하는 식이다. 각 칸에는 −999 이상 999 이하의 정수만 입력할 수 있다. 수현이가 버추얼 친구들을 만나러 버추얼 세계로 떠날 수 있게 도와주자.
입력
정수 a, b, c, d, e, f가 공백으로 구분되어 차례대로 주어진다. (−999≤a,b,c,d,e,f≤999)
문제에서 언급한 방정식을 만족하는 (x,y)가 유일하게 존재하고, 이 때 x와 y가 각각 −999 이상 999 이하의 정수인 경우만 입력으로 주어짐이 보장된다.
출력
문제의 답인 x와 y를 공백으로 구분해 출력한다.
using System;
using System.Linq;
public class Program
{
public static void Main()
{
int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
int a = numbers[0];
int b = numbers[1];
int c = numbers[2];
int d = numbers[3];
int e = numbers[4];
int f = numbers[5];
int x = (e * c - b * f) / (a * e - b * d);
int y = (d * c - a * f) / (b * d - a * e);
Console.WriteLine(x +" "+ y);
}
}다른 사람의 흥미로운 풀이
그냥 -999부터 999까지 전부 다 대입해도 풀리는 문제였다. 생각 안하고 빠르게 풀기 위해선 저 방법도 나쁘지 않을듯하다.
코딩테스트 : 1018번 체스판 다시 칠하기
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
using System;
using System.Linq;
public class Program
{
public static void Main()
{
int[] MN = Console.ReadLine().Split().Select(int.Parse).ToArray();
int M = MN[0]; // 행
int N = MN[1]; // 열
float min = int.MaxValue;
string[,] matrix = new string[M, N];
// 행 순서대로 읽어야 함.
for (int i = 0; i < M; i++)
{
string s = Console.ReadLine();
// 각 행의 문자열을 열 단위로 저장
for (int j = 0; j < N; j++)
{
matrix[i, j] = s.Substring(j, 1);
}
}
// 8x8 체스판 탐색 (범위 제한)
for (int i = 0; i <= M - 8; i++)
{
for (int j = 0; j <= N - 8; j++)
{
// 왼쪽 위가 흰색일 경우
float count1 = 0;
// 왼쪽 위가 검정색일 경우
float count2 = 0;
for (int x = 0; x < 8; x++)
{
for (int y = 0; y < 8; y++)
{
char expectedNumber1 = ((x + y) % 2 == 0) ? 'W' : 'B';
char expectedNumber2 = ((x + y) % 2 == 0) ? 'B' : 'W';
char currentColor = matrix[i + x, j + y][0];
if (currentColor != expectedNumber1)
{
count1++;
}
if (currentColor != expectedNumber2)
{
count2++;
}
}
}
float currentMin = MathF.Min(count1, count2);
if (currentMin < min)
{
min = currentMin;
}
}
}
Console.WriteLine(min);
}
}
약 두 시간 소요... 난 바보다.
행과 열을 또 혼동해서 한참 시간 잡아먹고, 그냥 한 줄 짜리 String으로 풀어보려다가 또 시간 잡아먹고..
다른 사람의 흥미로운 풀이
Bool 값으로 이 풀이를 훨씬 깔끔하게 하신 분이 계신다. 결국 나올 수 있는 string 값은 'w', 'B' 뿐이므로 그냥 True, false의 값으로 저장해버리고, 참이면 플러스... 이런식으로 해결하셨다.
이건 나중에 다시 풀어봐야겠다.