DJ's Blog

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 우와.. 알고나면 답안이 세상 간단해보이는데, 알기전엔 참 힘든 문제이다. 어느부분이 힘들었냐? 하면 13번째 줄 이라고 단언할 수 있다. min 값부터 max 값 까지 제곱수로 나누어 떨어지지 않는 수, 즉 제곱수의 배수를 제외 하고 남은 수가 몇개인지를 구하는데... 에라토스테네스의 체를 사용하면 될거같은데.. 문제는 그냥 사용하기에는 max 값이 너무나 크다는 것이었다.. 힌..

알고리즘 2022. 4. 14. 10:28

https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 이 문제는.. 코드 답안만 봐서는 정말로 헷갈리는 문제였고, 직접 풀어보고 이해할 수 있었다. 문제의 접근방법은, 행이나 열 중 하나를 선택해서 뒤집을 수 있는 모든 경우의 수를 먼저 수행한다.(18번째 줄, 2^n의 경우의 수 발생) 나는 열을 뒤집는 모든 경우의 수를 수행하는 것을 선택했다. 열을 뒤집는 경우의 수는 k 값으로 선택됐으니, 그안에서 각 행마다(21~32번줄) 뒤집을지 말지(..

알고리즘 2022. 4. 13. 14:11

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 요즘 CODE 책을 읽으면서 이진수에 대해 흥미가 생겨 이진수를 이용해서 푸는 방법으로 풀어보았다. 10을 11번 곱한 수를 12로 나눈다고 할 때, 10을 11번이나 곱하는 것은 비효율적이므로 2진수를 이용해서 구해보자. 11을 이진수로 나타내면 1011 → 2^3 + 2^1 + 2^0 → 8 + 2 + 1 10^11 = 10^(8+2+1) = (10^8) x (10^2) x (10^1) 11을 이진수로 나타낼때 1011 이면, 11을 2로 나누어 나머지가 1..

알고리즘 2022. 4. 11. 11:49

https://www.acmicpc.net/problem/12872 12872번: 플레이리스트 첫째 줄에 수빈이가 만들 수 있는 플레이리스트의 경우의 수를 출력한다. 경우의 수가 매우 커질 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 위 문제는.. 접근하는 방법을 도저히 모르겠어서 답을 보고 한참을 생각했다가 풀었는데, 중간에 잘못생각한 코딩 몇글자..?로 한참을 또 생각한 문제였다ㅠㅠ n개의 곡이 있고, p개의 곡을 들을건데, 중복되는 노래의 경우 반드시 m개의 곡을 사이에 두고 플레이 해야한다... 먼저, m개의 곡을 사이에 두고를 빼고 중복된 값이 안된다고 가정하면 가능한 경우의 수가 3개 곡인 경우 -> 3 x 2 x 1 5개 곡인 경우 -> ..

알고리즘 2022. 4. 11. 09:58

https://www.acmicpc.net/problem/1413 1413번: 박스 안의 열쇠 첫째 줄에 박스와 열쇠의 개수 N과 폭탄의 개수 M이 공백을 사이에 두고 주어진다. N은 20보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. www.acmicpc.net 박스안의 열쇠문제... 사이클 수를 구하는 방법을 내가 이해한 걸 적어본다. 폭탄을 터뜨려서 모든 박스를 열 수 있는 확률을 구하는 문제... 폭탄을 터뜨려서 열 수 있는 박스는 사이클이 형성된 박스이다. 예를들어 3개의 박스 1, 2, 3 번 박스 안에 열쇠가 아래와 같이 되어있다면, (1) 1 / 2 / 3 -> 사이클 3개(박스를 모두 열려면 폭탄이 3개가 필요) (2) 1 / 3 / 2 -> 사이클 2개(박스를 모두 ..

알고리즘 2022. 4. 8. 09:43

https://www.acmicpc.net/problem/10564 10564번: 팔굽혀펴기 각각의 테스트 케이스에 대해서, 동혁이가 응원하는 팀이 득점한 점수의 최댓값을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는.. 접근을 잘 하면 쉽게 풀 수 있는 문제인데 그 접근을 잘못해서 한참 헤맸다ㅠㅠㅠㅠ... DP로 풀기 위해, unique한 값을 가진 변수를 구해야 하는데 d[index][score] = sum 을 생각했다.. index는 상관없이 d[score][sum] = true 로 접근하면 바로 풀 수 있었다.. 일단 index, score은 unique 하지 않다... index는 아에 필요없다. 각 점수를 받고 그 점수가 누적되면서 그 점수, 누적..

알고리즘 2022. 4. 7. 09:23

https://www.acmicpc.net/problem/3012 3012번: 올바른 괄호 문자열 예제 1의 경우 다음이 가능하다. ({([()])}), ()([()]{}), ([([])]{}) www.acmicpc.net 위 문제는 백준 10422번 괄호 문제와 매우 비슷한 문제이나 푸는데 꽤나 애를 먹었다.. 애를 먹은 부분은 시간초과 난 부분과 답이 맞은거 같은데 틀렸습니다 나오는 부분이었는데.. 풀면서 어려웠던 부분을 기록해보려고 한다. 먼저 시간초과 난 부분, 메모리를 저장해주는 2차원 배열 d[][] 에 -1값으로 초기값을 세팅해주고(46~48번째 줄) 이후 저장된 값이 있으면, 재귀함수를 이어가는 것이 아니라 저장된 값을 바로 리턴해주지 않아서였다.(16~17번째 줄) 위와 같이 고치기 전에..

알고리즘 2022. 4. 6. 10:10

https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 백준 출근기록 문제는 12969번 ABC 문제를 풀었다면 풀수 있는 문제이다. 나는 ABC 문제와 출근기록 문제를 풀면서, 다음에 한번 더 풀 때 꼭 잊어버릴것 같은 한줄이 있어서 그부분을 잊지 않기 위해 적어본다. 위 코드에서 바로 16번줄!! 기존에 이미 한번 지나갔으나, 결국엔 정답과 맞지 않아서 넘어간 변수 d 는 true로 남아있으므로 이미 true인 변수 d는 false로 ..

알고리즘 2022. 3. 31. 14:59