본문 바로가기

알고리즘345

[백준 31910] 이진수 격자 (C++) https://www.acmicpc.net/problem/31910문제각 칸에 0 또는 1이 적혀 있는 N×N격자가 있다. 인선이는 1행 1열에서 출발해 N행 N열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 1행 1열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다.N행 N열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 M을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 M=13이다. 인선이가 계산하게.. 2025. 1. 25.
[백준 9324] 진짜 메시지 (C++) https://www.acmicpc.net/problem/9324문제 스파이들은 사령부와 통신하기 위해서 SMTP(비밀 메시지 전송 프로토콜)를 사용해 비밀 회선으로 전자 메시지를 보낸다. 메시지가 적들에 의해 조작되어 보내진 것이 아닌 진짜 메시지라는 것을 표시하기 위해 모든 메시지는 회선에 노이즈가 있었거나 발신 측에서 손을 떨면서 메시지를 보낸 것처럼 변형되는데, 이 변형 알고리즘은 메시지를 가로채는 자들이 우연히 변형 규칙을 흉내 낼 수 없을 정도로 정교하다. 또한 요원들의 머리에 총구가 겨눠져 강제로 메시지를 말한 경우 간단히 실수를 의도적으로 넣어 이 메시지가 강제로 쓰인 메시지라는 것을 알려줄 수 있다.알고리즘대로 정확하게 변형된 메시지는 각 문자가 세 번째 등장할 때 한 번 더 문자가 삽입.. 2025. 1. 24.
[백준 16174] 점프왕 쩰리 (Large) (C++) https://www.acmicpc.net/problem/16174문제‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.‘쩰리’.. 2025. 1. 23.
[백준 16946] 벽 부수고 이동하기 4 (C++) https://www.acmicpc.net/problem/16946문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.각각의 벽에 대해서 다음을 구해보려고 한다.벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 세어본다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. 출력맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인.. 2025. 1. 22.
[백준 22353] 헤이카카오 (C++) https://www.acmicpc.net/problem/22353문제일상을 바꾸는 단어, 헤이카카오는 카카오엔터프라이즈의 인공지능 플랫폼 Kakao i에 기반한 인공지능 비서 어플리케이션이다. 헤이카카오를 사용하면 음악 검색, 길 찾기, 외국어 번역 등 다양한 기능들을 말 한 마디로 이용할 수 있다.2020 헤이카카오 연말 결산에 따르면, 헤이카카오가 "고마워", "안녕" 다음으로 많이 들은 말은 "끝말잇기 하자"였다고 한다. 방에서 핸드폰을 만지작거리던 이하도 심심풀이로 헤이카카오와 끝말잇기를 해 보기로 했다.이하는 끝말잇기를 가볍게 여러 판 플레이하고 통계를 냈다. 그 결과 끝말잇기를 한 판 하는 데에는 a분이 걸리며, 현재 자신이 이길 확률은 d%라는 사실을 알게 되었다. 이하는 자신의 승률에 실.. 2025. 1. 21.
[백준 20500] Ezreal 여눈부터 가네 ㅈㅈ (C++) 문제욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.참가자 여러분도 궁금하지요?안 궁금함? 15ㄱ 입력 N이 주어진다. 출력문제의 답을 1 000 000 007로 나눈 나머지를 출력한다.제한 1 ≤ N ≤ 1515 문제 풀이 dp 문제. 15로 나누어 떨어지려면 5로 나누어 떨어져야 하고, 3으로도 나누어 떨어져야 한다. 따라서 맨 마지막 자릿수는 5 고정이고, 모든 자릿수의 합이 3의 배수여야 한다.dp를 이용하여 i자리 자릿수 중 3으로 나누었을 때 나머지가 0, 나머지가 1, 나머지가 2인 수의 개수를 구한다. i-1자리 자릿수에 1 또는 5를 붙여 i자리 자릿수를 만든다. 1은 나머지가 1추가 되.. 2025. 1. 20.
[백준 14405] 피카츄 (C++) https://www.acmicpc.net/problem/14405문제피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다.문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문자열인지 아닌지 구하는 프로그램을 작성하시오. 입력첫째 줄에 문자열 S가 주어진다. 문자열은 알파벳 소문자로 이루어진 문자열이며, 길이는 5000을 넘지 않는다. 출력문자열 S가 "pi", "ka", "chu"를 이어 붙여서 만들 수 있으면 "YES"를 아니면 "NO"를 출력한다. 문제 풀이문자열 문제. 피카츄가 발음할 수 있는 음절은 pi, ka, chu이다. 따라서 문자열의 앞에서부터 2자 혹은 3자를 .. 2025. 1. 19.
[백준 14575] 뒤풀이 (C++) https://www.acmicpc.net/problem/14575문제도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지(Li)와, 어느 정도 마시면 힘든지(Ri)를 물어보았다. 각 사람은 Li미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri를 초과하는 술을 마시면 천국으로 가버릴 수도 있다. 도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다. 마침 도현이의 통장엔 정.. 2025. 1. 18.
[백준 1106] 호텔 (C++) https://www.acmicpc.net/problem/1106문제세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.각 도시에는 무한 명의 잠재적.. 2025. 1. 17.

티스토리툴바