시간초과
-
BOJ 17143 : 낚시왕백준 문제풀이/etc 2020. 5. 4. 18:28
문제 문제 풀어보기 풀이 최근에 출제되는 삼성 기출문제는 거의 80% 가 시뮬레이션 문제입니다. 시뮬레이션은 순차적으로 진행되는 프로그램을 그대~로 구현하는 문제입니다. 이러한 문제들은 복잡한 알고리즘을 요구하지 않기 때문에 빠른 이해력과 정확한 설계만 한다면 대부분 푸실 수 있는 문제들입니다. 하지만 시뮬레이션에선 항상 시간 초과의 늪에 빠지게 됩니다. 이문제도 그랬는데요. 그러한 시간초과를 해결하는 방법이 바로 모듈러 연산입니다. 예를 들어 봅시다. 철이는 1초마다 숫자를 하나씩 증가하면서 말하고 있는데, 3의 배수일때마다 박수를 친다고 합니다. 그럼 1억초 이후에 철이는 몇 번 박수를 칠까요? 라는 문제를 풀때 저희는 1초 일때 박수를 치는지 안치는지 2초 일때 박수를 치는지 안치는지 3초 일때 박..
-
BOJ 10942 : 팰린드롬?백준 문제풀이/Dynamic Programming 2020. 1. 23. 15:46
문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E로 나타낼 수 있으며, 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은 팰린드롬이다. 자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대..