백준 알고리즘 풀이 (11) 썸네일형 리스트형 [백준] 25187번 : 고인물이 싫어요 (C++) https://www.acmicpc.net/problem/25187문제재형이는 청정수를 좋아하고 고인물을 싫어한다. 오늘도 청정수를 구하기 위해 물탱크들이 있는 마을에 방문한다.마을에는 N개의 물탱크가 존재하고, 각 물탱크는 청정수 또는 고인물을 저장하고 있다. 그리고 물탱크는 공급의 편의를 위해 M개의 파이프로 서로 연결되어 있다.청정수를 얻기 위해 K번 물탱크에 방문했을 때, K번 물탱크와 K번 물탱크에서 0개 이상의 파이프를 거쳐 이동 가능한 물탱크 중, 청정수가 담긴 물탱크의 수가 고인물이 담긴 물탱크의 수보다 더 많은 경우 청정수를 얻을 수 있다.방문할 예정인 물탱크에 대한 정보가 주어질 때마다, 청정수를 얻을 수 있는지 구해보자. 입력첫째 줄에 물탱크의 수 N(1≤N≤100000)과 파이프의 .. [백준] 27468번 : 2배 또는 0.5 배 (C++) https://www.acmicpc.net/problem/27468 문제KSA 학생들은 아래 조건을 만족하는 길이가 N인 수열을 좋아한다. 1,2,⋯,N이 A에 정확히 한 번씩 등장한다.임의의 인접한 세 수 A_i, A_{i+1}, A_{i+2}에 대해 |A_{i+1}−A_i|=|A_{i+2}−A_{i+1}|×2 또는 |A_{i+1}−A_i|=|A_{i+2}−A_{i+1}|×0.5이다.정수 N이 주어졌을 때, 조건을 만족하는 수열이 존재하는지 판별하고 있다면 아무거나 찾아보자.입력첫 번째 줄에 정수 N이 주어진다.출력첫 번째 줄에 조건을 만족하는 수열이 존재한다면 YES, 아니라면 NO를 출력한다.만약 그러한 수열이 존재한다면, 두 번째 줄에 N개의 정수 A1,A2,⋯,AN출력한다.정답이 여러 개 존재.. [백준] 1082번 : 방 번호 (C++) https://www.acmicpc.net/problem/1082 문제스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.입.. [백준] 9963번 : N - Queen (C++) https://www.acmicpc.net/problem/9663 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.예제 입력 1 8예제 출력 1 92N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 구하는 유명한 문제이다.제한시간이 10초로 그냥 단순하게 백트래킹을 하면 되는 문제 처음에는 board[n][n]을 만들고 퀸이 배치 될 때 마다 board[i][j] + 퀸이 공격 가능한 칸에 +1을 하여 방문했음을 표시하였지만, 칸마다 방문여부를 표시하는 것은 .. [백준] 17070번 : 파이프 옮기기 1(C++) https://www.acmicpc.net/problem/17070 문제유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 .. [백준]18429번 :근손실(C++) https://www.acmicpc.net/problem/18429 문제웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트.. [백준] 2206번 : 벽 부수고 이동하기(C++) https://www.acmicpc.net/problem/2206문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 .. [백준] 1024번 수열의 합 - 시그마 합 공식, 이진탐색 알고리즘(Python) https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 사용 알고리즘 수열의 합공식을 이용해서 리스트를 구하는 조건문을 작성하였다. 풀이 합이 N이면서 길이가 최소 L인 음이 아닌 정수 리스트의 시작 값을 k라고 한다면, 리스트는 항상 [k k+1 k+2 ... k+m](m은 L-1보다 큰 임의의 정수)의 값을 가질 것이다. 따라서 우리는 아래의 식을 만족하는 k, m값을 찾아주면 된다. 이때, 우리는 등차수열의 유한합 공식이 다음과 같다는 것을 알고있다. 위 공식을 식에 대입시켜 보자. 따.. 이전 1 2 다음 목록 더보기
