나그네

20206번: 푸앙이가 길을 건너간 이유 문제 https://www.acmicpc.net/problem/20206 20206번: 푸앙이가 길을 건너간 이유 첫째 줄에는 정수 A, B, C (-10,000 ≤ A, B ≤ 10,000, -100,000 ≤ C ≤ 100,000)가 주어진다. 해당 숫자들은 좌표 평면 상에서 Ax+By+C=0 형태로 표현되는 푸앙이가 지나가는 직선 상의 경로을 나타낸다. (단 www.acmicpc.net 풀이 Ax+By+C=0 형태의 표현되는 직선 상의 경로가 직사각형을 통과하는지 여부를 묻는 문제입니다. Ax+By≤-C 또는 Ax+By≥-C로 식을 바꾸어 생각해야합니다. 문제에서 테두리 위로만 지나가는 경우는 위험지역을 통과하지 않는 것으로 간주한다고 했으므로 등호를 포함해..

14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 문제 https://www.acmicpc.net/problem/14715 14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) 첫 번째 줄에 처음 주어진 슬라임의 에너지 K (2 ≤ K ≤ 1, 000, 000) 가 주어진다. www.acmicpc.net 풀이 간단한 정수론 문제입니다. K = A × B 형태로만 분할할 수 있으므로 최종적인 형태는 소인수분해된 형태임을 예측할 수 있습니다. 즉, K가 100일 때, 100 = 2^2 × 5^2 이므로 4개의 소인수로 분해됩니다. 이 문제는 흠집이 제일 많이 생긴 슬라임의 흠집 개수의 최소를 구하는 문제입니다. 흠집을 최소화하기 위해선 가능한한 완전 이진 트리 형태로 분할하는..

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 문제 https://www.acmicpc.net/problem/24265 24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 i=1~n-1까지 총 n-1번 반복되는 for문을 수행합니다. 이 for문 내부에선 j=i+1~n까지 총 n-i번 반복되는 for문을 수행합니다. 이중 for문 내부의 코드는 i=1일 때 j=2~n, i=2일 때 j=3~n, ... , i=n..

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 문제 https://www.acmicpc.net/problem/24264 24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 풀이 MenOfPassion 함수는 어떤 n에 대해서 n회 반복되는 for문을 수행합니다. 이 for문 안에서 다시 n회 반복되는 for문을 수행합니다. 따라서 이중 for문 안의 코드1은 n^2번 수행됩니다. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수는 2입니다. 코드 #inclu..

29158번: 큰 수 만들기 게임 문제 https://www.acmicpc.net/problem/29158 29158번: 큰 수 만들기 게임 성현이와 지훈이는 큰 수 만들기 게임을 하고 있다. 성현이는 양의 정수 $N$이 적힌 카드 $1$장이 들어 있는 주머니를 들고 있다. 지훈이는 성현이의 카드를 몰래 본 다음 성현이의 카드에 적힌 $N$ www.acmicpc.net 풀이 큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다. 각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다. 먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2..

29159번: 케이크 두 개 문제 https://www.acmicpc.net/problem/29159 29159번: 케이크 두 개 $(0,0),(0,1),(1,0),(1,1)$이 네 쪽지점인 직사각형과 $(2,1),(3,2),(3,1),(3,2)$가 네 꼭지점인 직사각형을 동시에 이등분하는 직선의 방정식은 $y=\frac12 x+\frac14$이다. www.acmicpc.net 풀이 두 직사각형 각각의 중심 좌표를 구하고, 두 점을 지나는 일차방정식을 구하는 문제다. 분수 형태의 출력 형식 때문에 애를 먹은 문제다. 먼저 일차방정식의 형태를 보면 y - y1 = ((x2 - x1)/(y2 - y1))(x - x1)이다. y = Px + Q 형태로 나타냈을 때 P와 Q를 출력하는 문제다. 먼저 기울기 P ..

28683번: 피타! 피타! 피타츄! 문제 https://www.acmicpc.net/problem/28683 28683번: 피타! 피타! 피타츄! 포켓몬스터를 좋아하는 종우는 포켓몬스터를 연구하다가 포켓몬스터가 상당히 수학적이고 코딩과 밀접한 관련이 있는 게임이라는 것을 알게 되었다. 모든 이동은 유클리드 공간에 평행하게 이 www.acmicpc.net 풀이 대회 당시에는 문제를 해결하지 못했다. 친구의 설명으로 문제를 해결하고 에디토리얼을 참고했다. 몇 가지 조건을 나누어 문제를 해결할 수 있다. 1. n이 제곱수인 경우 √n은 정수다. 임의의 정수 a에 대해 (√n, a, √(n+a^2))이 직각삼각형을 이루고, 두 변의 길이가 √n과 a로 정수이므로 무한하다. 2. n이 제곱수가 아닌 경우 나머지..

28682번: 재우야 임관하자 문제 https://www.acmicpc.net/problem/28682 28682번: 재우야 임관하자 인터랙티브 문제의 경우 출력을 하고, 언어에 따라 아래와 같은 명령어를 바로 다음에 적어 출력 버퍼를 flush해 줘야 한다. C: fflush(stdout); C++: fflush(stdout); 혹은 std::cout > n; string a[] = {"swimming", "bowling", "soccer"}; for (int i = 0; i < n; i++) // 그냥 swimming만 n번 출력해도 된다. cout

28444번: HI-ARC=? 문제 https://www.acmicpc.net/problem/28444 28444번: HI-ARC=? 첫째 줄에 각 문자에 들어갈 값 $H, I, A, R, C$ ($0 \leq H,I,A,R,C \leq 100$, $H,I,A,R,C$는 정수) 가 공백을 사이에 두고 순서대로 주어진다. www.acmicpc.net 풀이 값을 입력받고 식을 구성해서 출력하는 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int h, i, a, r, c; cin >> h >> i >> a >> r >> c; cout

28702번: FizzBuzz 문제 https://www.acmicpc.net/problem/28702 28702번: FizzBuzz FizzBuzz 문제는 $i = 1, 2, \cdots$ 에 대해 다음 규칙에 따라 문자열을 한 줄에 하나씩 출력하는 문제입니다. $i$가 $3$의 배수이면서 $5$의 배수이면 “FizzBuzz”를 출력합니다. $i$가 $3$의 배수이지만 $5$ www.acmicpc.net 풀이 대회 도중에는 isdigit 함수가 생각이 안났다.. 문자의 첫번째 글자가 ascii 코드 기준 숫자인지로 문자열 전체가 숫자인지 판단했다. 입력받은 a, b, c 중 반드시 하나는 숫자이기 때문에 각각에 대해 숫자인 경우에 +1, 2, 3을 해서 조건에 맞게 출력했다. 코드 #include us..