1. 문제 설명 https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 2. 아이디어 이 문제는 직접 그려서 해보는 게 빠르다. 여기서 재밌는 점은 N이 1인 경우를 제외하고는 그 어떤 곳에서도 주사위가 4면 이상 노출되는 면은 없다. 4면이 노출되면 문제가 다소 까다로워지겠지만 3면이면 사실 그냥 처음에 입력받은 값을 오름차순으로 정렬해서 가장 작은 3개의 값만 골라오면 된다. 그리고 솔직히 이 다음은 어느정도 노가다가 들어갔..

1. 문제 설명 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 아이디어 치즈 문제(BOJ - 2636)와 굉장히 유사한 문제지만 이번에는 처음에 주어진 그래프를 통해서 익은 토마토의 위치를 시작지점으로 큐에 담아야 한다. 또한 그 과정에서 토마토가 들어있지 않은 구간은 방문한 구간으로 처리하여 bfs로 접근을 방지한다. 이러면 사실상 준비는 끝났고 그냥 bfs 돌려버리면 된다. 다만 여기서 토마토 정보는 따로 건들지 않았..

1. 문제 설명 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 2. 아이디어 이게 왜 골드4..? 라는 생각이 들 정도로 아이디어나 알고리즘이나 딱히 특출날 게 없는 문제. source와 sink가 고정정으로 좌상단, 우하단으로 정해져 있기 때문에 dfs를 사용하여 각 지점에서 종점으로 갈 수 있는 경우를 dp로 저장해가면서 마지막에 (0,0)에 할당되는 결과값을 출력하면 끝난다. 다만, 내가 여기서 처음 틀렸던 이유는 cache를 0으로 ..

1. 문제 설명 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2. 아이디어 최악의 경우에 1024 * 1024 크기의 표에서 값을 100,000 구해야 하는데 제한 시간은 1초밖에 안 된다. bfs를 사용해서 매번 연산과정을 거쳐 값을 구하는 건 너무 미련한 짓이다. 이런 문제는 곧 dp를 사용해서 풀이해야 함을 알 수 있어야 한다. 우선 N*N 크기의 리스트에 [n-1][n-1]을 기점으로으로 [..