https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class P15658 { static int[] nums; // 계산 숫자 배열 static int[] arr; s..
>문제 너무 길다 생략! www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net > 핵심 탐색 알고리즘 (이분탐색) >풀이과정 맨 처음에 그냥 문자열 배열으로 주욱 입력받은 다음에 이중반복문으로 뺑뺑이 돌리려고 했는데 시간초과가 나서 방법을 수정해야 했다.. O(n^2)보다 빠른 탐색 방법이라면 이분탐색(O(logn))이 쉽고 대표적이기에 이분탐색을 사용했다. 이분탐색을 사용하려면 우선 배열이 정렬되어있어야 하므로 list외에 추가로 s..
[C] 백준 | 2670번 코드 - 연속부분최대곱
>문제 www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net > 핵심 DP 혹은 이중반복문 >풀이과정 이중 반복문을 돌려서도 시간초과 없이 풀어진다 다만 DP로 푸는것이 시간복잡도 면에서 훨씬 효율적인 알고리즘이라 할 수 있겠다 >깨달은점 DP는 아직 어렵다 근데 풀다보니까 뭔가 느낌은 오는 것 같다. 아직 더 많이 풀어봐야할듯 >코드 #define _CRT_SECURE_NO_WARNINGS #include double dp[10002]; int ma..
[C] 백준 | 17626번 코드 - Four Squares
>문제 www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net > 핵심 DP 아니면 삼중반복문 >풀이과정 어려웠다. 어떻게 풀어야하나 도통 생각이 안나서 그냥 반복문을 돌려서 어거지로 풀었는데 나는 DP로 풀고싶었다. 근데 도저히 생각이 안나서 다른사람 아이디어를 보고나서야 DP 방식이 이해가 됐다. dp 배열에는 제곱수를 표현하는 최소 개수가 들어간다. dp[0] = 0, dp[1] = 1으로 초기화. 그리고 반복문을 돌면서 d..
[C] 백준 | 9655번 코드 - 돌 게임
>문제 www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net > 핵심 규칙찾기 >풀이과정 처음에 보고 와 막막하다.. 생각했는데 경우의 수를 적어보다 보니까 매우 쉬운 규칙성을 발견해서 아주 쉽게 풀 수 있었다;; 그 규칙은 A, B 순서대로 돌을 가져간다고 했을때 돌의 개수가 짝수이면 반드시 A가 이기고 돌의 개수가 홀수이면 반드시 B가 이긴다. 돌을 한개 가져가나 세개 가져가나 A는 반드시 짝수 위치에 오게 되므로 돌의 개수가 짝수이면 반드시 A가 이기는 게임인것이다 베스킨라빈스 31 게임을 할때도 1개와 3개 중에서 뽑아갈 수 있다고 조건을 건다면 나중에 시작하는 사람이 반드시 ..
[C] 백준 | 1010번 코드 - 다리 놓기
>문제 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 핵심 조합 (nCr) >풀이과정 DP 문제라길래 풀어봤는데 막상 풀고나니까 DP보다는 조합 문제인 것 같다. 처음에는 DP처럼 풀려고 팩토리얼을 dp 배열에 저장해놓고 nCr 계산할 때 꺼내쓰려고 했었는데, 문제의 조건에 따르면 최대 30! 까지 구해야 할 수 있는데 이 30!은 unsigned long long 자료형을 사용해도 다 담을 수가 없는 범위이기 때문에 그렇게 할 수가 없다..! 그래서 ..
[C] 백준 | 13301번 코드 - 타일 장식물
>문제 www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net > 핵심 피보나치 수열 DP long long형 >풀이과정 피보나치 수열을 이용해서 풀 수 있다. n = 5일때 길이는 (5 * 2) + ((3+5) * 2) 다시말해 dp[n] = (dp[n] * 2) + ((dp[n-1] + dp[n]) * 2) (배열 인덱스가 0부터 시작하므로 아래 코드에는 n-1, n-2로 이용함.) 근데 이게 초등부 문제라는데 경악을 금치못했다 요즘 초등학생들은 천재들밖에 없나...
[C] 백준 | 12037번 코드 - Polynesiaglot
>문제 www.acmicpc.net/problem/12037 12037번: Polynesiaglot (Small1) In Case #1, suppose that the only vowel is a and the only consonant is h. Then the possible valid words of length 4 are: aaaa, aaha, ahaa, haaa, haha. In Case #2 (which would not appear in the Small dataset 1), suppose that the two vowels are a a www.acmicpc.net > 핵심 DP 자음 앞에는 모음만 올 수 있다 >풀이과정 와 어렵다 다이나믹 프로그래밍 기법을 사용하지만 내 머리는 다이나믹하..