본문 바로가기

dp74

[백준] 10942번 : 팰린드롬? (C++) 10942번 : 팰린드롬? 문제) 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다. .. 2024. 3. 8.
[백준] 5569번 : 출근 경로 (C++) 5569번 : 출근 경로 문제) 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대로 번호가 1, 2, ..., h로 매겨져 있다. 서쪽에서 i번째 남북 방향 도로와 남쪽에서 j번째 동서 방향 도로가 만나는 교차로는 (i, j)이다. 상근이는 교차로 (1, 1)에 살고 있고, 교차로 (w, h)에 있는 회사에 차로 다니고 있다. 차는 도로로만 이동할 수 있다. 상근이는 회사에 최대한 빨리 가기 위해서, 동쪽 또는 북쪽으로만 이동할 수 있다. 또, 이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉.. 2024. 3. 8.
[백준] 20544번 : 공룡게임 (C++) 20544번 : 공룡게임 문제) 시험을 맞아 하이테크관에서 급하게 벼락치기를 하던 도현이는 오늘도 인터넷 연결 없음 창을 마주하게 되었다! 위 창에서 스페이스바를 누르면 공룡게임을 플레이 할 수 있다. 공룡게임의 규칙을 설명하자면 공룡은 계속해서 앞으로 전진한다. 맵에 무작위로 장애물인 선인장이 등장하는데 적절한 타이밍에 스페이스바를 누르면 점프를 해서 선인장을 뛰어넘을 수 있다. 점프를 적절한 타이밍에 누르지 못하면 공룡이 선인장에 부딪히게 되어 게임이 종료된다. 이 때, 게임 시간에 비례한 점수를 얻는다. 의욕이 팍 떨어져 버린 도현이는 그대로 스페이스바를 눌러 공룡게임을 플레이 하였지만, 수많은 문제 풀이로 다져진 그의 피지컬 앞에선 게임이 너무 쉬워서 도저히 게임이 끝나지를 않았다! 원래의 공룡 .. 2024. 3. 8.
[백준] 3933번 : 라그랑주의 네 제곱수 정리 (C++) 3933번 : 라그랑주의 네 제곱수 정리 문제) 양의 정수는 많아야 4개의 제곱수로 표현할 수 있다고 한다. 이 이론을 라그랑주의 네 제곱수 정리라고 한다. 이 정리는 조제프루이 라그랑주가 1770년에 증명했다. 우리는 이 이론을 증명하거나 새로운 이론을 발견할 필요는 없고, n이 주어졌을 때 4개 이하의 양의 제곱수의 합으로 n을 만들 수 있는 경우의 수를 구하려고 한다. 경우의 수를 구할 때 제곱수의 순서가 바뀌는 경우는 같은 경우로 본다. 따라서 3^2 + 4^2 과 4^2 + 3^2는 같은 경우이다. N이 25일 때 4개 이하의 제곱수의 합으로 표현 할 수 있는 경우는 1^2 + 2^2 + 2^2 + 4^2, 3^2 + 4^2, 5^2 이렇게 3가지이다. 입력 : 입력은 최대 255줄이다. 각 줄.. 2024. 3. 8.

티스토리툴바