본문 바로가기
반응형

Problem Solving155

백준 1781 : 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net [ 문제풀이 ] 처음에는 데드라인이 현재 날짜 기준 이하인 문제들 중 가장 컵라면 개수가 많은 문제를 풀도록 하였다. 하지만 다음과 같은 반례가 존재하게 된다. 7 1 9 1 8 2 200 2 99 3 100 5 999 5 150 내가 생각한 방법은 1-9, 2-200, 3-100, 5-999, 5-150을 선택하게 되지만 정답은 2-200, 2-99, 3-100, 5-999, 5-150을 선택하는 것이다.. 2021. 7. 11.
백준 15483 : 최소 편집 https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net [ 문제풀이 ] 편집 거리 알고리즘으로 유명한 문제이다. dp 테이블을 다음과 같이 정의하자 dp[i][j] : A.substring(0,i+1)으로 B.substring(0,j+1)를 편집하는 최소횟수 만약 A의 i번째 문자와 B의 j번째 문자가 같다면 dp[i][j]의 값은 무엇일까? 두 문자열의 마지막 문자가 같기 때문에 마지막 문자에 관한 편집은 할 필요가 없다는 것을 알 수 있다. 즉, 마지막 문자가 없는 상태인 A의 i-1번째까지의 문자열로 B의 j-.. 2021. 7. 8.
백준 5213 : 과외맨 https://www.acmicpc.net/problem/5213 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net [ 문제풀이 ] 지문이 굉장히 길어서 이해하는데 조금 시간이 걸렸지만 결국 1번 타일부터 시작하여 각 타일들을 통해 이동할 수 있는 타일 중 번호가 가장 큰 타일의 최소 경로를 찾아주면 되는 문제이다. 이동할 수 있는 타일 간의 거리는 1이기 때문에 BFS를 수행해주면 된다. 다만, 각 타일마다 이동할 수 있는 경로를 어떻게 설정해줄 .. 2021. 7. 7.
백준 2662 : 기업투자 https://www.acmicpc.net/problem/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net [ 문제풀이 ] 배낭 문제와 거의 비슷한 유형으로 dp를 사용하여 해결해주면 된다. 먼저 다음과 같이 dp 테이블을 정의하자. dp[i][j] : 1~j번째 기업까지 i원을 사용했을 경우 최대 이익구하고자 하는 값 그렇다면 점화식은 어떻게 될까? 잘 생각해보면 현재 기업에 i원을 투자하기 위해서는 이전 i-1기업까지 투자한 금액이 N-i원을 초과해서는 안된다. 그래야 현재 기업에 i원만큼 투자할 수 있기 .. 2021. 7. 6.
백준 2211 : 네트워크 복구 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net [ 문제풀이 ] 문제의 1, 2번 조건을 살펴보면 정점들이 최소 경로의 간선으로 모두 연결되어야 하기 때문에 다익스트라 알고리즘을 사용하라는 의미이다. 간선은 경로를 저장해줘서 출력해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; imp.. 2021. 7. 5.
백준 1525 : 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net [ 문제풀이 ] bfs를 수행하여 0을 옮길 수 있는 모든 경우를 탐색해주면 된다. 퍼즐의 상태를 쉽게 관리하기 위해 3x3 배열이 아닌 1차원의 문자열 형태로 관리하였다. 퍼즐의 상태와 중복 방문을 관리해줄 방법만 생각해낸다면 쉽게 해결할 수 있을 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStrea.. 2021. 7. 4.
백준 16437 : 양 구출 작전 https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net [ 문제풀이 ] 골드 2 난이도 치고는 굉장히 간단한 문제이다. "각 섬에서 1번 섬으로 가는 경로는 유일하다"라는 문장 때문에 모든 섬을 연결한 상태는 그래프가 아닌 트리라는 것을 알 수 있다. 따라서 1번 노드를 기준으로 dfs를 수행하며 말단 노드부터 거슬러 올라오면서 양 or 늑대인 경우를 처리해주면 쉽게 해결할 수 있다. 주의해야 할 점은 정답의 범위가 int 범위를 넘.. 2021. 7. 3.
[프로그래머스] 불량 사용자 https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr [ 문제풀이 ] 모든 banned_id에 대해서 가능한 user_id를 구해준 후 중복을 제외하고 만들 수 있는 조합의 개수를 구해주면 된다. import java.util.*; class Solution { List[] list; Set set; Set ans; int answer, ul, bl; public int solution(String[] user_i.. 2021. 7. 1.
백준 2239 : 스도쿠 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net [ 문제풀이 ] 전형적인 백트래킹을 활용한 완전 탐색 문제이다. 모든 보드를 차례대로 탐색하여 1~9까지의 수를 채워나가면서 스도쿠 퍼즐이 완성될 수 있는지를 확인해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReade.. 2021. 7. 1.
반응형

티스토리툴바