본문 바로가기
반응형

백준499

백준 2580 스도쿠 c++, Kotlin (백트래킹) 문제 출처 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1.. 2021. 11. 10.
백준 1053 팰린드롬 공장 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. www.acmicpc.net 문제 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능) 어떤 위치에 있는 문자를 삭제 어떤 위치에 있는 문자를 교환 서로 다른 문자를 교환 1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 .. 2021. 11. 9.
백준 1106 호텔 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다. 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 .. 2021. 11. 9.
백준 15483 최소 편집 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 문제 두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다. A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다. 삽입: A의 한 위치에 문자 하나를 삽입한다. 삭제: A의 문자 하나를 삭제한다. 교체: A의 문자 하나를 다른 문자로 교체한다. 두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 .. 2021. 11. 7.
백준 11403 경로 찾기 c++ (플로이드 와샬) 문제 출처 : https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 .. 2021. 11. 6.
백준 4963 섬의 개수 c++, Kotlin (bfs) 문제 출처 : https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은.. 2021. 11. 5.
백준 9177 단어 섞기 c++ (bfs) 문제 출처 : https://www.acmicpc.net/problem/9177 9177번: 단어 섞기 입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어 www.acmicpc.net 문제 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자. 첫 번째 단어 : cat 두 번째 단어 : tree 세 번째 단어 : tcraete 보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어.. 2021. 11. 4.
백준 14462 소가 길을 건너간 이유 8 c++ (dp) 문제 출처 : https://www.acmicpc.net/problem/14462 14462번: 소가 길을 건너간 이유 8 존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만 www.acmicpc.net 문제 존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다. 농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼.. 2021. 11. 3.
백준 14916 거스름돈 c++ (탐욕법) 문제 출처 : https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.. 2021. 11. 2.
반응형

티스토리툴바