본문 바로가기

acmicpc68

[BOJ] #1748 수 이어 쓰기 1 시간 제한 메모리 제한 정답 비율 1초 128MB 56.357% 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 문제 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 1234567891011121314151617181920212223... 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오. 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. 해결 1~n까지 자리수를 계산하여 ans에 일일이 더해주었다. 코드 메모리 시간 1984KB 232ms 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. 2020. 4. 23.
[BOJ] #14502 연구소 시간 제한 메모리 제한 정답 비율 2 초 512 MB 54.624% 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 문제 0 : 빈 칸 1 : 벽 2 : 바이러스 로 나타내며, 바이러스가 퍼저나가는 것을 막기위해 반드시 3개의 벽을 세워야 한다. 이 때 .. 2020. 4. 23.
[BOJ] #1953 팀배분 시간 제한 메모리 제한 정답 비율 2 초 128 MB 43.773% 1953번: 팀배분 첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속한 사람들을 출력한다. 단 답이 여러 가지 일 경우에는 한 가지만 출력하여도 좋다. www.acmicpc.net 문제 청팀과 백팀으로 두 팀을 나누어 팀전을 하려 한다. 하지만 서로 같은 팀을 하기 싫어하는 사람들이 생겼다. 이제 우리가 할 일은 다음과 같다. 사람들이 각각 싫어하는 사람들의 정보가 주어져 있을 때, 그 사람들의 요구를 수용하여 서로 싫어하는 사람은 같은 팀에 넣지 않으려 한다. 이 조건을 만족하여 n명의 사람들 두 팀.. 2020. 4. 21.
[BOJ] #1068 트리 시간 제한 메모리 제한 정답 비율 2초 128MB 25.526% 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. www.acmicpc.net 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다... 2020. 4. 17.
[BOJ] #2941 크로아티아 알파벳 시간 제한 메모리 제한 정답 비율 1 초 128 MB 46.116% 2941번: 크로아티아 알파벳 문제 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다. dž는 무조건 하나의 알파벳으로 쓰이고, www.acmicpc.net 문제 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어.. 2020. 4. 16.
[BOJ] #1021 회전하는 큐 시간 제한 메모리 제한 정답 비율 2 초 128 MB 43.582% 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net 문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와.. 2020. 1. 11.
[BOJ] #11052 카드 구매하기 시간 제한 메모리 제한 정답 비율 1초 256 MB 59.766% https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 구매하고 싶은 카드의 개수 N 과, 1 ~ N 개의 카드 묶음의 가격 P[1] ~ P[n]이 두 줄에 나타나게 된다. 따라서 P[1]은 카드 한 개를 구매했을 때의 가격, P[2]는 카드 두 개를 구매했을 때의 가격, P[3]은 카드 세 개를 구매했을 때의 가격이 된다. 이 때 카드 N 개를 갖기 위해 지불해야하는 금액의 최댓값을 출.. 2020. 1. 10.
[BOJ] #11722 가장 긴 감소하는 부분수열 시간 제한 메모리 제한 정답 비율 1 초 256 MB 64.883% https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net 가장 긴 증가하는 부분수열과 같은문제이다. 가장 긴 증가하는 부분수열은 0 →n 방향으로 순회했다면, 가장 긴 감소하는 부분수열에서는 n →0 방향으로 순회한다. 간단히 방향만 바꿔풀었다. 메모리 시간 1120 KB 0 ms 1234.. 2019. 12. 16.
[BOJ] #11053 가장 긴 증가하는 부분수열 시간 제한 메모리 제한 정답 비율 1 초 256 MB 37.230% 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net dp[i] 는 0~i 번 째까지 만들 수 있는 가장 긴 증가하는 부분수열의 길이이다. 0 부터 n까지 순회하는 i-반복문과, 그 안에 0 부터 i 번째까지 순회하는 j-반복문 으로 이중for문을 만들었다. arr[j] < arr[i] 를 만족하는 것들 중에서 dp[j] 가 가장 큰 것을 기억해뒀다가 .. 2019. 12. 16.

티스토리툴바