https://www.acmicpc.net/problem/17836다른 사람 풀이를 보다가 생각 못한 아이디어가 있어서 공유합니다. 🔗 문제 해석용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하..

푼 사람이 별로 없길래 오랜만에 작성해봅니다 ✌🏻https://www.acmicpc.net/problem/1400 🔗 문제 해석 조건이 있는 BFS 문제 도로 (N x M, N, M ≤ 20)`#` : 갈 수 있는 길`.` : 못 가는 길`[0-9]` : 조건이 있는 교차로신호주기: A (동서 - ), B (남북 | )시작 방향 - , |교차로의 신호등은 동서 방향과 남북 방향, 두 개의 신호가 주기적으로 켜진다. 교차로의 신호는 초기에 동서 방향 또는 남북 방향이 될 수 있다. 교차로의 신호 주기를 나타내는 값 "a b"는 동서 방향의 신호가 a 시간 켜지고, 남북 방향의 신호가 b 시간 켜짐을 의미한다.예를 들어, 초기에 남북 방향의 신호가 켜지고 주기 값이 "2 3"이면, 차량이 1-3 시간..

🔗 문제 해석 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.제국의 참모인 당신은 제국의 ..

🔗 문제https://www.acmicpc.net/problem/1106 세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.각 도시에는 무한 명의 잠..

🗒️ 문제 https://www.acmicpc.net/problem/18808 ❓설명 스티커를 겹치지 않고 붙였을 때, 스티커가 모눈종이를 차지하는 칸의 수를 출력하라! [스티커 붙이는 법 💖]스티커는 순차적으로 붙인다.스티커를 회전시키지 않고 모눈종이에서 떼어낸다.다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90..

🔗 문제https://www.acmicpc.net/problem/1497 최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오. ✏️ 풀이 조건N ≤ 10, 자연수M≤ 50, 연수 알고리즘조합비트 마스킹몇 대의 기타를 조합해야지 모든 곡을 다 칠 수 있을까? 즉, n개 중에 r개를 뽑았을 때 최대 곡수를 전역으로 저장해뒀다가 최소 r를 갱신해주면 된다.이 때 유의할 것은 최대 M이 50이며, 모든 곡들을 순회하면 속도가 느리다는 것이다. 그래서 바로 비트 마스킹을 떠올릴 수 있었고 int의 범위가 넘어가기 때문에 `long long`을 해주는 것이 포인트다.어렵지 않지만 굳이 풀이를 쓰는 이유는 반드시 마스킹할 때 `1LL`에서 밀어주기. 간과했다가 틀렸습..

스터디 문제인데 괜찮은 문제인 것 같아 리뷰를 씁니다.스터디원 모두 다양한 방법으로 풀었기도 하고, 질문 게시판에 글이 몇 개 없기도 해서 작성합니다.🔗 문제https://www.acmicpc.net/problem/16166 ✏️ 풀이이 문제의 핵심은 큰 수의 역 번호를 가지고 어떻게 최소 환승 횟수를 구하는 가이다.그리고 호선과 역의 연결을 어떻게 자료구조를 저장할지 생각해 보는 것!  1. Mapper 설계N의 최대 크기는 2^31승인데 입력 타입을 int로 받아도 정답이 잘 나온다. (테스트 케이스가 부실?..)HashMap mapper;Long -> [hashing] -> idx (고작 0~100임)문제를 잘 보면 호선은 최대 10개, 각 호선마다 최대의 10개의 역즉, 호선의 값은 크지만 최대..

🔗 문제https://www.acmicpc.net/problem/1654 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고..

🔗 문제https://www.acmicpc.net/problem/17271  ✏️ 풀이알고리즘 분류: DP 난 처음부터 DP라는걸 눈치 채지 못 하고 일단 나이브하게 완탐으로 풀었다. DFS라서 `2^N`이나 되기 때문에 시간초과다. 일단 이렇게 해서 답이 나왔다는 걸 알았으니까 이 논리를 가지고 dp로 바꾸면 된다.import java.io.*;import java.util.*;public class Main { static int N, M; static int answer = 0; static Set visited = new HashSet(); static void comb(int sum, String pattern) { if(visited.contains(p..

🔗 문제https://www.acmicpc.net/problem/1253  ✏️ 풀이실질적으로 N은 2000개 밖에 되지 않지만 나이브하게 생각할 수 있는 for문으로는 O(N^3)으로 무리가 있다.2개의 값을 가리켜야 한다는 점을 고려하면 투포인터가 적합하다. #시간 복잡도 계산투포인터를 사용하기 위해 정렬이 필요하다. ⇒ O(nlogn)N개의 값에 대한 최대 N번을 고려한다. ⇒ O(N^2) 수열에 음수가 있을 때 답이 나오지 않는다는 것을 발견했다3-3 0 3// 1 (0)3-2 -1 -1// 1 (-2)   i번째 수열은 0부터 N-1의 범위를 모두 보아야 한다. 이 때 자기 자신을 가리키지 않도록 조건 체크를 반드시 해주어야 한다.    💾  소스#include #include #includ..