문제 풀이49 백준 9020 C#) 골드바흐의 추측 짝수를 두 소수의 합으로 나타내되 차이가 가장 작은 것으로 출력하라고 한다. 상당히 어려운 조건처럼 보이지만 이는 사실 힌트에 가깝다. public static class PS { private static int[] nArr; private static bool[] isNotPrime; public static void Main() { //최댓값에 대하여 에라토스테네스의 체를 생성하면, 이후 반복하여 만들 필요가 없다 int nMax = 0; int t; (int left, int right) ans; //입력 t = int.Parse(Console.ReadLine()); nArr = new int[t]; for (int i = 0; i < t; i++) { nArr[i] = int.Parse(Cons.. 2022. 5. 7. 백준 1929 C#) 소수 구하기 소수임을 판별해야 하는 숫자가 많을 때는, 이를 일일이 확인하기 보다는 에라토스테네스의 체를 사용하는 것이 좋다. class Program { static void Main() { //입력 string[] input = Console.ReadLine().Split(); int m = int.Parse(input[0]); int n = int.Parse(input[1]); //에라토스테네스의 체 bool[] isNotPrime = EratosSieve(n); //출력 StreamWriter sw = new(new BufferedStream(Console.OpenStandardOutput())); for (int i = m; i 2022. 5. 7. 백준 11653 C#) 소인수분해 소인수분해 자체는 어렵지 않지만 이를 얼마나 빠르게 처리할 수 있는지가 관건이다. int n = int.Parse(Console.ReadLine()); int n_sqrt = (int)Math.Sqrt(n); int m = 2; while (n != 1) { if (n % m == 0) { Console.WriteLine(m); n /= m; n_sqrt = (int)Math.Sqrt(n); continue; } m++; if (m > n_sqrt) { Console.WriteLine(n); break; } } 정수 n이 주어지면 이를 m으로 계속 나눠보면 된다. 그러다 더 이상 m으로 나누어떨어지지 않으면 m을 1 증가시키고 다시 시도한다. (도중에 m이 합성수가 될 수도 있지만 어차피 나누어떨어지지 .. 2022. 5. 6. 백준 2839 C#) 설탕 배달 3과 5를 최소로 조합하여 숫자 n을 만드는 문제이다. int n = int.Parse(Console.ReadLine()); int cnt = 0; while (n % 5 != 0 && n > 0) { n -= 3; cnt++; } Console.Write(n >= 0 ? cnt + n / 5 : -1); 그냥 n에서 3을 계속 빼주다가 5의 배수가 되는 시점에서 멈추면 된다. 혹시라도 n이 0보다 작아진다면 이는 3과 5로 조합할 수 없는 숫자라는 뜻인데, 그럴 경우는 n이 1, 2, 4, 7일 때만 가능하다. 이외에는 전부 조합이 가능하니 미리 예외 처리를 해도 좋다. 참고로 5의 나머지로 경우의 수를 나누는 풀이도 있다. 다만 반복문을 돌려도 금방 빠져나오기 때문에 속도에는 큰 차이가 없을 것이다. 2022. 5. 6. 백준 10250 C#) ACM 호텔 문제 자체는 간단한데 지문이 상당히 길어 헷갈리기 쉽다. StreamWriter sw = new (new BufferedStream(Console.OpenStandardOutput())); int t = int.Parse(Console.ReadLine()), y, x; int[] hwn; for (; t > 0; t--) { hwn = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); y = hwn[2] % hwn[0]; x = hwn[2] / hwn[0]; if (y == 0) y = hwn[0]; else x += 1; sw.WriteLine(y * 100 + x); } sw.Close(); 문제를 읽어보면 "102 호보다 2101 호를 더 선호한다.. 2022. 5. 5. 백준 2869 C#) 달팽이는 올라가고 싶다 간단한 일차부등식 문제이다. int[] abv = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); int a = abv[0]; int b = abv[1]; int v = abv[2]; int day = (int)Math.Ceiling((double)(v - b) / (a - b)); Console.Write(day); 구하고자 하는 답을 x로 설정한다면 아래 식처럼 표현할 수 있다. 여기서 a, b, v는 문제에서 설명하였다. 이 문제의 포인트는 두 가지인데, 하나는 달팽이의 이동 거리가 (a - b) * x가 아니라는 점이다. 왜냐하면, 달팽이가 미끄러지는 횟수는 올라가는 횟수보다 항상 한 번이 적기 때문이다. 달팽이는 정상에 오르기 전까지는 계속 .. 2022. 5. 4. 백준 2292 C#) 벌집 벌집에 층이 있다고 생각하자. (아래 사진 참조) 1층 : 1 2층 : 2 ~ 7 3층 : 8 ~ 19 ... 여기서 각 층마다 끝번호를 구하면 차례대로 1, 7, 19, 37, 61 ... 이 되는데 이를 점화식으로 표현하면 층수 n에 대하여 A(1) = 1, A(n) = A(n - 1) + 6(n - 1) 이라고 할 수 있다. 이 점화식을 이용하여 문제를 풀어보자. int n = int.Parse(Console.ReadLine()); int last = 1; int cnt = 1; while (n > last) { last = last + 6 * (++cnt - 1); } Console.Write(cnt); 위에서 구한 점화식으로 끝번호 last를 계속 구한다. 여기서 층수는 cnt이다. last가 .. 2022. 4. 27. 백준 1316 C#) 그룹 단어 체커 문제는 간단하다. 같은 알파벳은 반드시 붙어있어야 한다는 것이다. int n = int.Parse(Console.ReadLine()); int cnt = 0; string s; while (n-- > 0) { s = Console.ReadLine(); cnt++; for (int i = 0; i 1) { cnt--; break; } } } Console.Write(cnt); 내 아이디어는 이러하다. 문자열 "aaabbaa"에서 a를 검사한다고 치자. 그럼 현재 a와 제일 가까운 다음 a의 인덱스 차이를 구할 수 있을 것이다. 이때 그 차이가 1이라면 a는 서로 붙어 있다는 뜻이 되지만 1보다 크다면 그렇지.. 2022. 4. 27. 이전 1 2 3 4 5 6 7 다음
