문제 링크 https://www.acmicpc.net/problem/17252 ◆문제 해결 및 설명◆ 문제 : 3의 거듭제곱의 합으로만 이루어져 있다면 YES, 아닐 시 NO를 출력하여라. 알고리즘 분류 : 수학, 부르트포스 알고리즘, 사칙연산 첫째 줄에 2,147,483,647보다 작거나 같은 음이 아닌 정수 N이 입력된다. 기본 int로는 해결 할 수 없어 int64_t를 헤더를 통해서 선언해 사용하였다. ※ 0은 삼삼한 수가 아니다. 풀고 검색해보니 생각보다 푸는 법이 많았다는 걸 알 수 있었다. 첫째. 3^N > 3^(N-1) + ... + 3^(0) 내가 푼 방법인데, 3진수를 cpp에서 지원하지 않기 때문에 이를 구현하지 않고 풀 방법이 있나 생각하다 쓰게 되었다. 아래 표는 3의 거듭제곱을 ..
문제 링크 https://www.acmicpc.net/problem/15686 ◆문제 해설 및 설명◆ 문제 : 세준이는 책을 원래 자리에 놓아야 한다. 한 번에 M개의 책을 들 수 있다. 책들과 세준이의 시작 위치는 0이다. 책들의 위치는 세준이의 걸음을 기준으로 제공된다. 이때 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 구하라. (단, 모든 책을 놓고 나서 0으로 돌아올 필요는 없다.) 이 문제는 그리디 알고리즘으로 풀었다. 예제 입력을 보기 쉽게 나타내면 아래 그림처럼 나온다. 세준이가 들 수 있는 책의 갯수가 1일 때, 각각 모든 위치에 가는 것(편도)을 계산하고 제일 먼 위치만 제외하고 x2를 해주었다. (갔다가 책을 가지러 다시 와야 하기 때문에 거리가 두 배가 된다.) 가장 큰 값을 제..
문제 링크 https://www.acmicpc.net/problem/15686 ◆문제 해결 및 설명◆ 문제 : 수열을 주고, 어디 부터 어디까지가 펠린드롬 이냐 묻는 질문에 대답하는 문제 펠린드롬이란 거꾸로 읽어도 똑같은 문장이나 단어를 뜻한다. 따라서 직접 뒤집어서 비교하거나, 포인터를 통해서 문자가 같은지 판별해주면 되는데 이 문제는 수열의 크기 최대 2,000, 질문의 개수 최대 1,000,000 이며 시간 제한이 0.5초 이다. 위에서 이야기한 두 방법으로는 풀 수 가 없다. 다이나믹 프로그래밍으로 풀 수 있는데 기준을 잡고 기준이 펠린드롬일 때, 좌우로 하나씩 증가 했을 때 좌우가 같은 문자열이라면 그 문자는 펠린드롬이다. abcba에서 c가 기준인것이 보일 것이다. 좌우로 하나 늘린 bcb도 ..
문제 링크 https://www.acmicpc.net/problem/1911 ◆문제 해결 및 설명◆ 문제 : 물 웅덩이와 널빤지의 갯수와 첫 줄에 제공하고, 물 웅덩이의 길이를 제공할 때, 최소 널빤지 사용 갯수를 대답하라. 힌트를 보고 처음에는 아무생각 없이 구현으로 풀었다. 그랬더니 바로 메모리 초과가 딴! (문제 풀기전에 메모리와 시간을 확인 해야겠죠?) 그럼 이걸 수학적으로 풀어야 한다고 생각이 들었고, 그럼 물 웅덩이의 시작 부분을 찾아서 널빤지를 깔고 널빤지가 끝나는 위치를 저장한 다음, 저장한 위치에다가 널판지를 계속 설치를 하고, 이후 다음 물 웅덩이의 시작 부분이 저장된 널빤지가 끝나는 위치보다 작다면 널빤지가 끝나는 위치부터 널판지를 설치하는 코드를 작성하였다. ◆코드 전문◆ #incl..
