잡담연구소

www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1

www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net IDEA DP를 풀고나서 풀었더니 또 DP스럽게 생각을 하게 돼버렸다. 난 초반에 문제 이해가 잘 안됐는데 문제 설명을 다시 해보자면 K개 이상의 라이언 인형 = 1 을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력하는 문제다. -> 어차피 가장 작아야하므로 라이언 인형이 k개일때의 부분집합의 크기를 생각해주면 된다. N= 10, K =3일 때, 1 2 2 2 1 2 1 2 2 1 이렇게 보면 라..

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net IDEA LIS 알고리즘을 이용하는 문제다. 최근에 공부했어서 그런지 보자마자 보이네 헿 기존 LIS의 알고리즘의 문제점은 길이는 알 수 있어도 그 길이에 해당하는 원소들을 알 수 없다는 것이었다. 11055번은 그걸 물어보는 문제같다. 어떤 원소들이 가장 긴 부분 수열을 이루는지! 수열의 크기가 1000이라서 시간 복잡도 O($n^{2}$) 풀이를 사..

www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 아... 이 문제도 3시간 안에 푸는 문제 중 하나였는데,,,, ㅜㅜㅜㅜ 이게 bfs로 풀릴 거라곤 생각도 못했다. 맨 처음에는 아 그리디네?? 왜 실버1이지?하면서 풀었다. 틀렸단다 아무리 봐도 틀릴 구석이 없는데,,,ㅜㅜ 맨 처음에 생각했던 건 입력받은 편의점 좌표들에 하나하나 옮겨가면서 이전 편의점과의 거리를 계산해 1000이하면 다음으로 넘어가고, 1000보다 크면 sad를 출력하는 거였다. 틀린코..

www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 아ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ AI 부캠 코테 준비하겠다고 1시간에 3문제 푸는 거 연습했는데,,,,꼴랑 한문제밖에 못풀었다,,,,,, 시험볼 때 엄청 긴장하는 체질인데 큰일이다,,,,,긴장안해도 한 문제라니,,,, 다리놓기 문제는 실버5라서 엄청 만만하게봤다. 딱 보자마자 ? 순열이네 역시~~ 이러면서 순열 코드를 짜고 돌렸는데 계속 시간초과가 뜨더라,,,,29C13같은 경우 답이 나오지도 않음 이 문제에선 최대 수가..

www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net IDEA 어려운 문제는 아니지만 나에게 큰 교훈을 준 문제다,,,ㅜ 문제 설명을 먼저하자면 두가지 조건을 만족시키는 0,1로만 이루어져있는 수의 개수를 구하는 거다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. DP문제라고 생각해 DP로 풀었다. 최근에 풀었던 쉬운 계단 수 문제랑 비슷해보여서 , DP[M][N] : 끝..