본문 바로가기

백준91

[백준/C,C++] 1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 해당 문제를 보고 DFS, BFS문제구나 생각을 했습니다. 관건은 동적계획법을 사용해 어떻게 연산 수를 줄이는 것인가인데 다른 고수분들의 풀이를 보고 참고해 풀었습니다. DP[y][x] = 현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수로 가정하고 이를 사용한다면 탐색의 횟수를 줄일 수 있습니다. 예제를 통해 적용해보겠습니다. 최초 출발 지점인 50에서 10으로 갈 수 있.. 2021. 7. 4.
[백준/C,C++] 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 개인적으로 11066번: 파일 합치기와 비슷한 문제라 느꼈습.. 2021. 7. 4.
[백준/C,C++] 11066번: 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 문제 예제인 40, 30, 30, 50을 보겠습니다. DP[start][end]를 start부터 end까지 합치는 최소비용이라 하고, psum[i]를 0부터 i까지의 파일을 합치는 데 드는 비용이라 했을 때 40, 30, 30, 50의 최소 비용은 다음과 같이 나타낼 수 있습니다. DP[1][4] = min(DP[1][1] + DP[2][4], DP[1][2] + DP[3][4], .. 2021. 7. 4.
[백준/C,C++] 10993번: 별 찍기 - 18 https://www.acmicpc.net/problem/10993 10993번: 별 찍기 - 18 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 풀이 위 그림처럼 별을 찍으면 되는 문제입니다. 재귀를 이용해 별을 찍는 문제들에서 배열에 값을 저장한 후 찍는 것이 아닌 해당 좌표에 '*' 이 출력돼야 하는지 공백이 출력돼야 하는지 바로 판단하여 출력하는 식으로 함수를 구현하려고 했고, 이번 문제 또한 배열을 쓰지 않는 방법으로 해결하였습니다. 가장 큰 삼각형 단계부터 가장 작은 삼각형 단계까지 재귀 호출합니다. 해당 좌표가 현재 삼각형 단계에서 '*' 로 출력될 자리인지 판단하고 아니라면 다음으로 작은 삼각형 단계로 재귀 호출하는데, 1 크기의 삼각형이 될 때까지 '*'.. 2021. 5. 18.

티스토리툴바