곽로그

문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net comment 컨디션에 상관 없이 문제를 풀었음 좋겠다. 예외케이스을 생각하지 못한다거나, 풀이가 생각났다고 바로 코딩하려는 습관이나, 풀때마다 풀이가 달라지지 않도록 더 연습 풀이 - 연속된 세 개의 계단을 모두 밟으면 안된다는 조건이 없다면 점화식 f(n) 을 n번째 계단을 오를 때의 최대 점수 라고 정의하는 경우 f(n) = max( f(n-1), f(n-2) ) + score[n] 이 된다. 실수한 것 - "연..

문제 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 전형적인 dp문제다. 이 문제의 점화식 f(n)을 00,1로 만들 수 있는 크기가 n인 2진수열의 경우의 수라고 하면 f(n) = f(n-1) + f(n-1)가 된다. f(n) 의 경우에 해당하는 수열의 마지막에는 00 또는 1이 올 수 있다. 00이 오게되는 경우 앞에는 n-2자리의 2진수열이 오게되고, 1 이 오는 경우에는 앞에 n-1 자리의 2진 수열이 온다. 따라서 f(n) 은 위의 두가지 경우를 ..

문제 www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 최신버전 alwaysbemoon.tistory.com/241 풀이 1. 행을 순회하면서 인접한/같은 색의 칸을 탐색한다 2. 인접한/ 같은 색의 칸의 색깔 위치를 바꾼다 3. 바꾼 위치에 대해서 가장 긴 연속하는 색의 갯수를 구한다 의 순서로 문제를 풀면된다. 이때 "인접한"의 조건은 한 칸을 기준으로 오른쪽 칸/ 아래칸과 비교를 한다. 이와같이 할 경우 시간복잡도는 N의 4제곱이 된다. 여기서 시간복잡도를 줄이는 방법은 바뀐 위치의 행, 열에 대해서만 가장 긴 연속하는 색의 갯수를 구하는 거다. 그럴경우, 가장 긴 연속하는 색의 갯..

문제 www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 풀이 1. 1씩 증가 시간제한이 2초이므로 하나씩 검사를 해도 시간초과가 나지 않을 확률이 크다. E,S,M으로 만들 수 있는 경우의 수는 15 * 28 * 19 이므로 1초보다 작다. 따라서 1씩 증가시킨 후 해당 E, S, M이 주어진 조건과 일치하는 지 확인하면 된다. 2. 나머지 정리 이용 위의 문제는 카잉달력의 방식과 비슷하다. 진법과 관련된 문제는 나머지 정리를 생각하자. 코드(1씩 증가) impor..

문제 www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 주의! 첫번째도 그렇고 두번째도 0때문에 틀렸다. 처음엔 number==0인 경우를 생각하지 않아서 틀렸다. number의 범위에서 가능한 모든 경우를 따지는 습관을 들이자. 위의 경우 number가 음이아닌 정수이므로 >0 뿐만아니라 0인 경우도 고려해줘야한다. 반례 0 10 0 1 2 3 4 5 6 7 8 9 public static boolean isValid(int number){ ..

문제 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 - 그림을 볼 필요 없이 수열을 보면 점화식을 구할 수 있다. f(n) = f(n-2) + f(n-3) (단 n=1,2,3일 때는 1) - 구한 점화식을 가지고서 topDown방식, bottomUp 방식으로 풀 수 있다. - 이때 주의해야할 점은 문제에서 주어지는 n은 "n번째"의 개념이기 때문에 메모이제이션의 배열 index와 구분해야한다. - 그리고 답의 범위는 long 코드 import java.io..

문제 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 각 폴리오미노를 대칭, 회전시켜 나올 수 있는 모든 경우에 대해 구했다. check 폴리오미노를 for문으로 ****를 체크하는 게 아니라 좀 더 쉽게 체크할 수 있는 방법이 있을 것 같다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.Outp..

문제 www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 풀이 1) 괄호가 쌍을 이루기 때문에 우선 괄호 쌍의 인덱스를 찾는다. - (0/(0)) 의 경우 인덱스0 과 인덱스 6가 쌍을 이루고, 인덱스 3과 인덱스 5이 쌍을 이룬다. - 괄호 쌍의 위치를 저장하기 위해 Pair 클래스를 만들고 이를 ArrayList pairs에 저장한다. //수식문자열을 char 리스트로 받기 originalExpression = br.readL..