목록Baekjoon (6)

수학과의 좌충우돌 프로그래밍

[C++] BAEKJOON 1890번 점프

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 처음에는 bfs 나 dfs 를 생각하기 쉬운 문제지만 dp 를 사용해서 해결해야하는 문제입니다. dp 배열을 생성하여 각 원소는 해당 지점까지..

알고리즘/C++ 2019. 9. 6. 02:19
[C++] BAEKJOON 5052번 전화번호목록

5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net Trie 자료구조를 사용하는 문제였습니다. Trie 자료구조란? [Algorithm] Trie 자료구조 KMP 알고리즘 에 이어서 문자열에서 검색에 위한 새로운 방법들을 알아보도록 하겠습니다. 이번에..

알고리즘/C++ 2019. 8. 26. 23:01
[C++] BAEKJOON 9007번 카누선수(ACM-ICPC 예선 Daejeon 2012

문제보기 9007번: 카누 선수 문제 국제 카누 경주 챔피언십 (International Canoe Sprint Championship : ICSC)가 머지 않아 개막된다. ICSC에서 인증하는 공식 보트는 C1, C2 그리고 C4로 구성되며, "C"는 카누를 그리고 숫자는 노를 젓는 사람의 수를 의미한다. 카누 경주는 잔잔한 물 위의 여러개로 구획된 직선 코스에서 이루어진다. ICSC에서는 국제 경기를 200m, 500m 그리고 1000m로 구분하고 있다. 한국 스포츠 학교(Korea www.acmicpc.net 쉽게 생각해서 4중 for 문으로 구현하면 쉽게 나올 수 있지만 시간초과에 걸립니다. n의 범위가 최대 10^3 까지 이고 4중 for 문이면 10^12 이고 1초 이상이므로 여러 테스트 케이..

카테고리 없음 2019. 8. 3. 13:59
[C++] BAEKJOON 9455번 박스(ACM-ICPC Daejeon 2013)

문제 보러 가기 9455번: 박스 문제 m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다. 그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다. 박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이 www.acmicpc.net ACM-ICPC 문제라고 하기에 쉽고 간단한 문제 였습니다. 박스는 각 column 에서만 이동을 할 수 있으므로 column 을 기준으로 나눠서 생각해주었습니다. 박스가 있을 경우, 바닥으..

알고리즘/C++ 2019. 7. 26. 02:57