목록분류 전체보기 (123)
풀이 보관함
🔗 문제 1937번: 욕심쟁이 판다 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓..
🔗 문제 1676번: 팩토리얼 0의 개수 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🖍 풀이 아래 블로그를 읽고 이해한 문제 🔗https://sdev.tistory.com/808 [C/C++] 백준 #1676 팩토리얼 0의 개수(수학) 이번 문제는 팩토리얼을 계산했을 때, 뒤에서부터 연속된 0의 개수를 세는 것입니다. 팩토리얼은 1부터 n까지의 곱을 계산한 것인데요. 20 팩토리얼만 해도 2,432,902,008,176,640,000 값이 나와서 정수 sdev.tistory.com 문제 조건이 N ≤ 500으로 factorial(500)을 하면 엄청나게 긴 숫자에 시간초과가 뜰 수 있다. ..
🔗 문제 11403번: 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 🖍 풀이 DFS를 이용하여 풀었다. N개의 각 정점으로 부터 DFS를 이용해 연결된 모든 정점을 visited로 표시했다. 여기서 DFS에서 사이클을 무한반복하지 않도록 방문하지 않은 정점으로만 가는 조건을 반드시 걸어주어야 한다. 💾 소스 #include const int MAX = 100 + 1; bool graph[MAX]..
🔗 문제 16137번: 견우와 직녀 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 문제 정리 (0, 0)에서 (N-1, N-1)로 최소 이동 시간 구하기 N (2 ≤ N ≤ 10) 상하좌우로 이동할 수 있으며 한칸 당 1분 소요 맵 구성요소 1: 이동할 수 있는 일반적인 땅 0: 건널 수 없는 절벽 2 이상의 수: 적혀있는 수 만큼의 주기를 가지는 오작교 오작교 특징 M(2 ≤ M ≤ 20)분 주기에만 오작교가 생성되어 절벽을 건너갈 수 있다. 🖍 풀이 문제 꼼꼼히 보기 오작교는 이처럼 매우 불안정하므로,..
🔗 문제 9376번: 탈옥 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 🖍 풀이 백준 9376번 탈옥 이 글을 보고 문제를 풀었습니다. 백준 9376번 탈옥 문제 링크입니다: https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모 jaimemin.tistory.com 생각해내야 하는 점 죄수 1이 죄수 2를 데리고 바깥으로 나가는 경우 죄수 2가 죄수 1을 데..
🔗 문제 10711번: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 🖍 풀이 문제의 조건 1 ≤ H, W ≤ 1,000 💡 파도가 몇번 칠지도 모르는데 이 범위를 2차원 배열을 이중포문으로 접근하는 건 TLE 가능성이 높다 그래서 모래가 있는 위치를 기준으로 BFS 했지만 시간 초과 🙂 시간 초과에 늪에 빠져서 🔗여기 에서 도움을 받았다. 처음엔 뭔 소리인지 모르겠어서 디버깅했더니 기존 코드의 실패 원인과 풀이 방법도 이해할 수 있었다. 📋 시간 초과 원인과 소스 코드 시..
🔗문제 1525번: 퍼즐 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 🖍풀이 한칸이 비워져있는 퍼즐을 순서대로 정렬하기 위한 최소 이동 비용을 구하는 문제 빈칸을 기준으로 사방의 셀을 옮겨가며 BFS방식으로 풀 수 있다. 🚩 2차원 배열이 아니라 문자열로 표현 빈칸을 기준으로 사방의 셀을 이동한다면 당연히 2차원 배열을 생각할 수 있지만, 이 풀이에서는 일련의 문자열로 취급해서 풀어주었다. 문자열에서 n 번째에 있는 빈칸을 x, y로 표현하는 법 문자열로 된 퍼즐을 BFS에 활용하는 법 최소 이동횟수를 구해야하기 때문에 이미 형성된 퍼즐을 큐에 넣으면 안된다. map이나 set를 활..
🔗 문제 17140번: 이차원 배열과 연산 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 크기가 3×3 (초기 배열 크기 3) 인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수
🔗 문제 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. => 격자의 범위가 벗어나는 법은 없다. 5칸 짜리에서 8번칸 이동해야하면 3칸에 위치시키면 된다. ==> x%=N 🖍 풀이 간단하게 정리하면 이렇게 풀 수있다. while(K--) { // 1. 파이어볼의 동시 이동 // 2. 파이어볼 나누기 } 1...
🔗 문제 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 🖍 풀이 문제를 보면 맵도 작고 CCTV 개수도 작기 떄문에 완전 탐색으로 풀어주었다. 소스를 보는게 빠를 듯하지만 설명을 해볼게요.. 현재..