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

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인걸 알아도 모르겠어서 결국엔 풀이를 찾아봤다. 아래 글을..

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 우선 처음에 딱 읽었을 때는 완탐 아니고서는 어떻게 풀지?? 싶었다. 중복을 허용하고, 순서가 바뀐 경우를 다르게 센다고 해서 중복 순열인가? 싶었지만 질문 게시판 살짝 보니 중복 조합이라고 하는데.. 잘 모르겠더라 그래서 일단은 예제를 가지고 고등학교 확통 시간을 떠올리며 직접 경우의 수를 세어봤다. K = 2일 때는 음 그렇구나 했는데 K = 4인 걸 다 써보고 나니까 뭔가 규칙이 보였다..!! 물론 어떻게 나올 지는 모르지만, K = 4에는 K = 1인 것, K = 2인 것, K = 3인 것도 다 포함이 되어 있었다. 그래서 뭔가 DP적으로 접근한다면,, N이랑 K를 냅색..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 읽기 처음에 봤을 때는 어제 풀었던 점프랑 뭔가 비슷하다는 느낌이 들었다. BOJ_S1_1890_점프 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수 rue-mi.tistory.com 하지만 점프의 경우에는 단순히 오른쪽, 아래쪽 방향으로만 이동이 가능했지만, 이 문제의 경우에는 상하좌우 모든 ..

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 읽기 처음에 딱 문제를 읽었을 때는 .. DP인 걸 인지하고 있었기 때문에 이중 for문을 쓰면서 채워나갈 수 있을 것이라 생각했다. 하지만 계속 읽다 보니 (0, 0)에서 시작하여 (N-1, N-1) 지점까지 DFS 또는 BFS를 써도 되지 않을까 하는 생각이 들었다. 일단 시뮬레이션을 해봤을 때 DFS가 더 맞는 것 같았지만, 문제의 조건에서도 볼 수 있듯이 판의 크기가 최대 100이다. DFS 쓰면 2^100…. 무조건 시간초과이다. 그래도..