본문 바로가기

전체 글210

[BOJ] 1328 : 고층 빌딩 문제 링크 1328번: 고층 빌딩 (acmicpc.net) 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 왼쪽에서 본 빌딩의 개수와 오른쪽에 본 빌딩의 개수가 주어졌을 때 가능한 빌딩 배치의 경우의 수를 구하는 문제. 참고 링크 https://beginthread.tistory.com/151 [ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드 https://www.acmicpc.net/problem/1328 목적 빌딩의 개수 N, 가장 왼쪽 또는 오른쪽에서 봤을 때 보이는 빌딩의 수 L과 R이 주어졌.. 2022. 3. 7.

[BOJ] 16236 : 아기 상어 문제 링크 16236번: 아기 상어 (acmicpc.net) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기상어가 엄마상어의 도움 없이 먹이를 먹고 성장할 수 있는 최대 시간을 출력하는 문제. 아기상어가 가장 가까운 먹이를 찾을 수 있도록 BFS 를 이용해야한다. 풀이 먼저, Count 라는 배열을 만들어서 1~6까지 크기의 물고기가 각각 몇 개 있는지 저장해두었다. 그리고 can_eat 라는 변수에 현재 상어가 먹을 수 있는 먹이가 몇 개 남아있는지를 체크했다. 만약 can_eat가 0이라면 더이.. 2022. 3. 5.

[BOJ] 2011 : 암호코드 문제 링크 2011번: 암호코드 (acmicpc.net) 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 암호가 주어졌을 때 가능한 해석의 수를 구하는 문제. 풀이 알파벳 A~Z를 1~26으로 암호화 하기로 했다. 띄어쓰기가 있다면 1 1 과 11을 구분할 수 있겠지만 암호에 띄어쓰기가 없기 때문에 암호가 11이라고 하면 "AA"와 "K"로 2가지로 해석 가능하다. 여기서 주의해야 할 점은 0은 아무런 암호도 아니기 때문에 해석이 불가능하다. 그렇기 때문에 10이 들어오면 1 0 으로 구분해서는 해석할 수 없고 10으로 해석해.. 2022. 3. 3.

[BOJ] 2225 : 합분해 문제 링크 2225번: 합분해 (acmicpc.net) 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP를 이용해서 숫자 N을 K개의 숫자 조합으로 만드는 경우의 수를 출력하는 문제. 풀이 DP[N][K] 배열을 만들어서 DP[Y][X] 에는 숫자 Y를 숫자 X개를 조합해서 만드는 경우의 수를 저장해야겠구나 생각했다. 일단 Bottom-up 방식으로 DP[0][1], DP[1][1], ... , DP[N][1], DP[0][2], DP[1][2], ... , DP[N][K] 이렇게 채워나가야겠다고 생각은 했지만, 점화식을 어떻게 해야할 지가 관건이다. 처음에는 예를 들어 DP[3][3]을 채우기 위해서는 DP[0][1] * DP[3.. 2022. 3. 2.

[BOJ] 1937 : 욕심쟁이 판다 문제 링크 1937번: 욕심쟁이 판다 (acmicpc.net) 풀이 문제를 보면 일단 DFS문제라는 것을 알 수 있다. 시작점에서 상하좌우 중 범위를 벗어나지 않으면서 현재 지점보다 값이 크면 그 지점을 방문한다. 그렇게 해서 더 이상 이동할 수 없을때 까지 도달했을 때 그 깊이 중 가장 큰 값을 찾는 문제이다. 그런데 모든 점에서부터 출발해서 최대값을 찾으면 될까?? 당연히 아니다. 그렇게 하게되면 이미 방문했던 지점을 시작점으로 같은 경로를 재탐색 하게되는 경우가 발생하기 때문에 시간초과가 난다. 그럼 어떻게 해야할까? DP를 이용해서 재방문을 하지 않도록 해야한다. 예제를 보자 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 (1,1)을 출발점으로 했을 때 주변에 자신(14.. 2022. 3. 1.

[BOJ] 2133 : 타일 채우기 문제 링크 2133번: 타일 채우기 (acmicpc.net) 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 대표적인 DP문제 2XN 타일링의 변형 문제. 풀이 2XN 타일과 다르게 여기서는 높이가 3이다. N = 1 : 3X1크기의 벽을 2X1 타일을 가지고 채울 수 없다. DP[1] = 0 N = 2 : 3X2크기의 벽을 2X1 타일을 가지고 채우는 경우의 수는 3. DP[2] = 3 N = 3 : 3X3 벽을 2X1 타일을 가지고 채울 수 없다. DP[3] = 0 여기서 무언가를 눈치 챌 수 있다. N이 홀수인 경우에는 벽을 완전히 채우지 못한다. 그렇기 때문에 N이 홀수라면 경우의 수는 0이다. N = 4 : N.. 2022. 3. 1.

[BOJ] 13392 : 방법을 출력하지 않는 숫자 맞추기 문제 링크 13392번: 방법을 출력하지 않는 숫자 맞추기 (acmicpc.net) 13392번: 방법을 출력하지 않는 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net DP 문제로 골드2라고 되어있지만 내 체감상으로 전에 풀었던 골드1 로봇 조종하기보다 어려운 것 같다. 오답 처음에는 DP배열을 2차원배열로 만들어서 생각했다. DP[돌리고있는 나사 번호][왼쪽으로 돌릴지 오른쪽으로 돌릴지] 이렇게 생각했다. 이전에 왼쪽으로 돌려서 만들어진 현재 보고있는 앞면이 있을 것이고, 오른쪽으로 돌려서 만들어진 현재 보고있는 앞면이.. 2022. 2. 25.

[BOJ] 2169 : 로봇 조종하기 문제 링크 2169번: 로봇 조종하기 (acmicpc.net) 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 최대한 탐사 가치의 합이 높게 N,M에 도달해야한다. 풀이 처음 나는 DP가 아닌 BFS의 방법으로 풀려고 했다. 임의의 어떠한 지점에 도달했을 경우 상황을 3가지로 나눠서 생각할 수 있다. 1. 왼쪽에서 왔다. 2. 오른쪽에서 왔다. 3. 위에서 왔다. 한 번 탐사한 지점은 다시 갈 수없기 때문에 왼쪽에서 온 경우 다시 왼쪽으로 갈 수 없다. 같은 논리로 오른쪽에서 온 경우 다시 오른쪽으로.. 2022. 2. 24.

[BOJ] 1509 : 팰린드롬 분할 문제 링크 1509번: 팰린드롬 분할 (acmicpc.net) 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 https://jk6722.tistory.com/6 [BOJ] 10942 : 팰린드롬? 문제 링크 10942번: 팰린드롬? (acmicpc.net) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에 jk6722.tisto.. 2022. 2. 24.

이전 1 ··· 18 19 20 21 22 23 24 다음

티스토리툴바