1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 읽기 일단 처음 문제를 읽었을 때는 그리디한 방식이 떠올랐다. 큰 숫자가 앞으로 올수록 좋을 것 같다고 생각했기 때문에, 맨 앞부터 숫자가 들어갈 자리를 정하고, 그 뒤의 숫자들 중에서 최댓값을 앞으로 땡기자는 생각이었다. 하지만 그렇게 했을 때 코드가 좀.. 여러가지 예외를 처리해 주면서 더러워졌을 뿐만 아니라, 잡지 못하는 예외 상황이 있었다. 그건 바로 숫자를 상호 “교환”하는 것이기 때문에, 최대인 수가 여러 개인 경우에 어떤 수와 교환할 지에 대한 문제였다. 이런 저런 문제와, 틀렸습니다 라는 문구, 그리고 질문 게시..

10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 읽기 일단 맨 처음에 문제를 읽었을 때는 투포인터가 생각났다. 구간을 입력 받을때마다 투포인터를 사용해서 팰린드롬인지 아닌지 판단하는 방식이다. 일단 코드를 빠르게 짜긴 했는데, 제출은 안했었다. 문제 입력의 크기를 봤다. N은 2000까지, 숫자는 100,000까지, 질문의 개수 M은 1,000,000까지 가능했다. 만약 맨 처음 푼 방식대로 제출했다면 시간 초과가 나왔을 것이다. 시간 복잡도가 M * N이 되기 때문에 제한 시간인 0.5초는 거뜬히 넘을 것 같다. 그렇게 생각하고 한 번 제출해..

7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 읽기 문제를 계속 읽다 보니 0/1 냅색 문제가 생각났다. 그래서 그 문제처럼 해보려고 했더니..@@ 메모리 용량의 범위가 너무 컸다. DP 2차원 배열을 선언한다면, 앱 개수 * 메모리 = 100x10,000,000 = 10억이었다. 절대 ! 안된다. 사실 메모리 계산하는 방법을 확실히 몰라서 찾아봤다. 글 읽기 - 메모리 초과... 128 mb이면 int형 몇개?까지 선언가능한가요?? 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 요약하면 ..

4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 문제 읽기 일단 처음 읽었을 때는 비트마스킹을 쓰는 문제인가? 싶었다. 맵의 크기가 20x20으로 작긴 하지만, 같은 칸을 여러 번 방문할 수 있다는 조건이 있었기 때문에, 큐에 visited를 계속 넣으면 잘못하면 메모리초과가 날 수도 있다고 생각했다. 그런데 비트마스킹을 어떻게 하는지 잘 생각이 안 나서 일단 다른 방법을 또 생각했다. 두 번째로 생각한 건, 더러운 곳을 각각 하나의 노드로 보고, 로봇 청소기(시작 위치)와 더러운 곳 사이의 거리, 그리고 노드간 거리..

11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 읽기 일단 문제를 처음 봤을 때 어제 푼 문제와 비슷하다고 느꼈다. 어제는 아래 파일 합치기 문제를 풀었었다. BOJ G3 11066 파일 합치기 JAVA 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종 rue-mi.tistory.com 그래서 비슷하게 DP로 접근했다! 문제 풀기 파일 합치..

11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 문제 읽기 일단 상당히 오래 걸렸다. DP 문제라고 하는데 DP 문제인지 전혀 몰랐다. 일단 처음에는 문제를 잘못 이해해서 마구잡이로 작은 것들끼리 합쳤다. 그랬더니 예제부터 틀려서 문제를 다시 읽어보고 깨달았다. 문제를 봤을 때는 약간 트리?모양이 생각났다. leaf 노드부터 하나씩 합쳐지는.. 그래서 내가 모르는 알고리즘인가 하고 분류를 봤는데.. 이게 머냐 DP였다. (자괴감 ㅠㅠ) 근데 DP인걸 알아도 모르겠어서 결국엔 풀이를 찾아봤다. 아래 글을..