일단 나는 벽을 부수지 않은 경우, 부순 경우를 각각 배열로 선언하고, 큐에도 (행, 열, 부순 여부) 를 넣어서 bfs를 돌렸다.
하지만 AC를 받은 후 내 코드 보다 훨씬 빠른 namnamseo님의 코드를 봤는데, 훨씬 간단하고 기발한 방법인 것 같아 여기 기록해둔다.
bfs를 두 번 돌리는데, 한 번은 시작점(1, 1)에서부터, 또 한 번은 끝점(n, m)에서부터 돌린다.
그렇게 돌려서 d1배열에는 시작점으로부터 각 점까지의 최단 거리, d2배열에는 끝점부터 각 점까지의 최단 거리를 구한는데, 이 때 벽을 만나게 되면 더 이상의 bfs는 하지 않기 때문에 벽을 만난 경우 벽 1개까지의 최단 거리를 구하게 된다.
그리고 나서 각 점까지의 최단 거리를 합쳐서 그 중 최소를 구하게 되면 최대 벽 1개를 부술 수 있을 때의 최단 거리가 구해진다!!
만약 벽이 여러개 있어서 경로가 없는 경우에는 처음 d1, d2배열을 큰 수로 초기화 해주는데, 적어도 d1, d2중 하나에는 큰 수가 갱신되지 않고 그대로 있게된다. 그래서 최종적으로 구한 값이 n * m보다 크면 -1을 출력해준다.
2018년 11월 2일 금요일
2018년 9월 11일 화요일
백준 9466 텀프로젝트, 재귀 주의 사항
dfs 재귀를 돌릴 때, visited값이 0이면 dfs함수를 재귀 호출하고, visited값이 1이면 flag값이 같은 경우만 dfs함수를 재귀 호출했는데...
if visited == 0
...
dfs
....
if visited == 1
...
dfs
...
이런 식으로 했다가 틀려서... 원인 찾는데 매우 힘들었다...
다행히 질문 검색에서
1
5
5 3 4 5 1
라는 반례를 올려주신 분이 계셨는데,
저 반례를 가지고도 원인 파악하는데 시간이 엄청 결렸다.
내가 착각하고 있던 것이... 당연히 if문 하나로만 들어갈 것으로 착각했는데, 알고보니, dfs함수를 타고 들어가면서 visited값이 업데이트(0 -> 1) 되어 그 다음 if문의 dfs로 또 들어가게 되는 것이었다...
그래서 두번째 if문을 else if로 고쳐서 AC를 받았다...
아주 기본적인 것인데도, 원인을 찾지 못하고, 반례를 알고도 직접 출력을 해보며 디버깅해보고 나서야 겨우 원인을 파악했다... 반성하자...
firstDuplicate 문제
CodeFights라는 사이트의 이름이 Code Signal로 바뀐 것 같다.
여기에서 본 문제 중 firstDuplicate라는 문제가 있는데,
지금은 문제가 좀 바뀐 것 같지만, 내가 처음 봤을 당시 문제는 다음과 같다.
양의 정수 수열이 입력으로 들어오면, 그 수열에서 처음으로 중복되는 수를 찾아서 리턴하는 문제인데, 여기서 처음으로 중복되는 수는 두 번째로 나온 수 기준으로 가장 앞에 있는 수를 뜻한다.
2, 1, 3, 5, 3, 2 가 있으면 처음으로 중복되는 숫자는 2가 아니라 3이된다.
그리고 중복되는 숫자가 없으면 -1을 리턴해야 한다.
얼핏보면 쉬워 보이지만, 조건이 하나 더 있다. 바로 메모리를 추가적으로 사용하지 않고 풀어야 한다는 것이다... (지금 들어가보면 그 조건이 사라져 있지만 이 조건이 있어야 어렵고 생각해볼만한 문제가 된다.)
boolean 배열이라도 하나 더 있어야 어떤 수가 이미 이 전에 나왔는지 체크를 할텐데... 어떻게 추가적인 메모리를 사용하지 않고 풀라는 걸까?
생각하다가 도저히 모르겠어서 다른 사람들의 모범 solution을 봤다.
추가적인 메모리는 사용할 수 없어도 주어진 수열은 활용할 수 있는데, 이것을 어떻게 활용하냐면,
입력으로 들어오는 수열의 수가 양의 정수라는 점, 입력으로 들어오는 수의 크기는 1이상 수열의 길이 이하라는 점을 이용해서, 해당 수를 주어진 수열의 index(해당하는 수 - 1)로 하여 index에 해당하는 값을 음수로 만든다. 그래서 그 index에 있는 수가 음수이면 그 수는 이미 한 번 나왔던 수라는 것을 알 수 있다.
참고로 음수로 바꿔서 체크하므로, 어떤 수 x를 볼 때는 x의 절대값으로 봐야한다.
예전에 한 번 본 문제 같기도 한데... 아무튼 전혀 생각을 못했다. 비록 수열이 양의 정수로 구성되어 있을 때만 가능하긴 하지만 정말 멋진 풀이같다.
여기에서 본 문제 중 firstDuplicate라는 문제가 있는데,
지금은 문제가 좀 바뀐 것 같지만, 내가 처음 봤을 당시 문제는 다음과 같다.
양의 정수 수열이 입력으로 들어오면, 그 수열에서 처음으로 중복되는 수를 찾아서 리턴하는 문제인데, 여기서 처음으로 중복되는 수는 두 번째로 나온 수 기준으로 가장 앞에 있는 수를 뜻한다.
2, 1, 3, 5, 3, 2 가 있으면 처음으로 중복되는 숫자는 2가 아니라 3이된다.
그리고 중복되는 숫자가 없으면 -1을 리턴해야 한다.
얼핏보면 쉬워 보이지만, 조건이 하나 더 있다. 바로 메모리를 추가적으로 사용하지 않고 풀어야 한다는 것이다... (지금 들어가보면 그 조건이 사라져 있지만 이 조건이 있어야 어렵고 생각해볼만한 문제가 된다.)
boolean 배열이라도 하나 더 있어야 어떤 수가 이미 이 전에 나왔는지 체크를 할텐데... 어떻게 추가적인 메모리를 사용하지 않고 풀라는 걸까?
생각하다가 도저히 모르겠어서 다른 사람들의 모범 solution을 봤다.
추가적인 메모리는 사용할 수 없어도 주어진 수열은 활용할 수 있는데, 이것을 어떻게 활용하냐면,
입력으로 들어오는 수열의 수가 양의 정수라는 점, 입력으로 들어오는 수의 크기는 1이상 수열의 길이 이하라는 점을 이용해서, 해당 수를 주어진 수열의 index(해당하는 수 - 1)로 하여 index에 해당하는 값을 음수로 만든다. 그래서 그 index에 있는 수가 음수이면 그 수는 이미 한 번 나왔던 수라는 것을 알 수 있다.
참고로 음수로 바꿔서 체크하므로, 어떤 수 x를 볼 때는 x의 절대값으로 봐야한다.
예전에 한 번 본 문제 같기도 한데... 아무튼 전혀 생각을 못했다. 비록 수열이 양의 정수로 구성되어 있을 때만 가능하긴 하지만 정말 멋진 풀이같다.
백준 3665 최종 순위
위상 정렬을 활용한다. graph와 indegree배열, queue를 사용한다.
문제의 예제와 같이 1등부터 시작해서 5등까지 팀이 5 - 4 - 3 - 2 - 1 인 경우,
그래프를 5 -> 4 -> 3 -> 2 -> 1 형태로 그리는 것이 아니라
5 -> 4 / 5, 4 -> 3 / 5, 4, 3 -> 2 / 5, 4, 3, 2 -> 1 처럼 각 정점에 도달하기 위해 거쳐야 하는 정점들을 모두 연결하게 그려서 각 정점이 서로 연결되어 있게(indegree도 그에 맞게 ++해주어야 한다) 한 후, 위상정렬을 진행한다.
indegree가 0인 것을 queue에 넣고, graph에 따라서 탐색하면서 다음 것의 indegree를 -1해주고 indegree가 0이면 queue에 넣어주는 식으로 진행한다.
만약 indegree가 0인 것이 없다면 모순이 있어 순위를 정할 수 없는 경우이고,
indegree가 0인 것이 동시에 여러개가 생긴다면 확실한 순위를 찾을 수 없는 경우로 볼 수 있다.
-----------------------
직접 구현해보니, 상대적 순위가 바뀌었다는 정보에 대해서 그래프를 수정해주는 것이 문제이다. 둘 중 누가 앞서 있는지도 알아야 하고, 그래프에 연결된 점을 일일이 다 보면서 찾아야 하는데 m이 25000이라... 그래프에 연결된 점이 최대 500개정도 된다고 하면 12,500,000번을 봐야 하는데, 테스트 케이스가 최대 100개라 시간초과가 날 위험이 있다.
그래서 vector를 사용하는 인접리스트 대신에 인접행렬을 써볼까한다. 일단 500 * 500이라 메모리는 문제없고, 인접행렬을 사용하면 일일이 다 볼 필요가 없고, 둘 중 누가 앞서 있는지도 쉽게 파악 가능하다.
아 참고로 인접리스트를 쓴다면, 소팅하여 이분탐색을 이용하는 방법도 있을 것이다.
---------------------------
계속 틀려서... 고민하다가 겨우 원인을 알아냈다.
바로 순위를 정할 수 없는 경우를 알아내는 부분에서 문제가 있었다. 나는 indegree가 0인 것이 없는지를 맨 처음에만 판단했다. indegree가 0인 것이 없으면 사이클이 생기는데, 사이클이 처음부터 생기지 않을 수도 있다. 일단 처음에는 indegree가 0인 것이 존재해서 queue에 들어가고, 계속 진행하다가 indegree가 0인 것이 없는 상황이 올 수가 있는 것이다...
반례)
input
1
4
1 2 3 4
2
3 4
2 3
output으로 "IMPOSSIBLE"이 나아야 하는데, 나의 틀린 코드로 돌리면 "?"가 나왔다.
그래서 그 경우를 처리했더니 AC를 받았다...
** 참고) 그리고 문제 관련 질문을 보던 중 확실한 순위를 찾을 수 없는 경우는 나올 수 없다는 답변이 있었는데, 실제로 그 답변을 잘 이해하진 못했고, 나도 정확히 증명은 못하겠지만 실제 예제나 반례를 만들어 보면서 확실한 순위를 찾을 수 없는, indegree가 0인 것이 동시에 여러개 생기는 경우를 만들지 못했었다.
백준 1915 가장 큰 정사각형
백준 Slack에서 고수분들이 말씀해주신 풀이를 적어보려 한다.
이 문제는 dp로 풀 수 있다.
주어진 배열에서 1로 된 가장 큰 정사각형의 크기를 구해야 하는데,
(r, c)를 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형과, (r+1, c)와 (r, c+1) 각각을 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형을 생각해보면,
d[r][c] = (r, c)를 가장 위의 가장 왼쪽으로 하는 가장 큰 정사각형의 한 변의 길이
라고 할 때,
d[r][c] = min(d[r+1][c], d[r][c+1]) + 1 이라고 볼 수 있을 것 같다.
하지만 d[r+1][c]와 d[r][c+1]이 같은 경우, 가장 오른쪽 아래 부분도 추가로 확인해봐야 한다. 가장 오른쪽 아래 부분이 0이면 d[r][c] = min(d[r+1][c], d[r][c+1]) 이 되는 것이고, 1이면 min(d[r+1][c], d[r][c+1]) + 1이 될 것이다.
시간복잡도는 O(N^2)정도가 나올 것 같다.
이 문제는 dp로 풀 수 있다.
주어진 배열에서 1로 된 가장 큰 정사각형의 크기를 구해야 하는데,
(r, c)를 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형과, (r+1, c)와 (r, c+1) 각각을 가장 위, 왼쪽으로 해서 만들 수 있는 최대 정사각형을 생각해보면,
d[r][c] = (r, c)를 가장 위의 가장 왼쪽으로 하는 가장 큰 정사각형의 한 변의 길이
라고 할 때,
d[r][c] = min(d[r+1][c], d[r][c+1]) + 1 이라고 볼 수 있을 것 같다.
하지만 d[r+1][c]와 d[r][c+1]이 같은 경우, 가장 오른쪽 아래 부분도 추가로 확인해봐야 한다. 가장 오른쪽 아래 부분이 0이면 d[r][c] = min(d[r+1][c], d[r][c+1]) 이 되는 것이고, 1이면 min(d[r+1][c], d[r][c+1]) + 1이 될 것이다.
시간복잡도는 O(N^2)정도가 나올 것 같다.
백준 8394 악수
처음에는 규칙을 찾아보려 했지만... dp로 풀 수 있다.
d[n] 을 사람의 수가 n명일 때, 악수를 하는 방법의 수
라고 하면
d[n]은 맨 끝의 사람이 악수를 하는 경우와 안 하는 경우로 나눌 수 있다.
악수를 하는 경우는 d[n - 2]가지 경우의 수가 있을 것이고,
악수를 하지 않는 경우는 d[n - 1]가지의 경우의 수가 있을 것이다.
d[n] = d[n - 1] + d[n - 2]가 된다.
d[n] 을 사람의 수가 n명일 때, 악수를 하는 방법의 수
라고 하면
d[n]은 맨 끝의 사람이 악수를 하는 경우와 안 하는 경우로 나눌 수 있다.
악수를 하는 경우는 d[n - 2]가지 경우의 수가 있을 것이고,
악수를 하지 않는 경우는 d[n - 1]가지의 경우의 수가 있을 것이다.
d[n] = d[n - 1] + d[n - 2]가 된다.
C, switch, case 문에서 || 연산자
백준 11723 집합 문제를 풀다가
swtich case문을 사용하면서 ||(or)연산자를 사용했는데
아래와 같이...
case 'a' || 'b':
내가 의도한 바는 'a' 또는 'b'인 경우에 그 케이스 문 안의 코드를 실행하는 것이었는데, 'a'가 오든 'b'가 오든 해당 case문 안으로 들어가지 않길래 찾아봤더니...
https://stackoverflow.com/questions/13226124/switch-case-with-logical-operator-in-c
저 경우에는 'a' || 'b'가 계산이 되어 True(1) 값으로 설정되기 때문에, 즉 case 1: 이 되기 때문에 'a', 'b'값 모두 통과를 할 수 없게 되는 것 같다.
----
아 그리고, switch문 안에서 case를 벗어난 부분에 코드를 입력하면 내려가면서 실행될 줄 알았는데 그렇지 않다... case문 밖에 있는 코드는 실행되지 않는다.
swtich(x) {
case 1:
......
break;
(x가 1이 아닌 경우에도 이 부분에 입력된 코드는 실행되지 않음)
case 2:
.......
break;
}
swtich case문을 사용하면서 ||(or)연산자를 사용했는데
아래와 같이...
case 'a' || 'b':
내가 의도한 바는 'a' 또는 'b'인 경우에 그 케이스 문 안의 코드를 실행하는 것이었는데, 'a'가 오든 'b'가 오든 해당 case문 안으로 들어가지 않길래 찾아봤더니...
https://stackoverflow.com/questions/13226124/switch-case-with-logical-operator-in-c
저 경우에는 'a' || 'b'가 계산이 되어 True(1) 값으로 설정되기 때문에, 즉 case 1: 이 되기 때문에 'a', 'b'값 모두 통과를 할 수 없게 되는 것 같다.
----
아 그리고, switch문 안에서 case를 벗어난 부분에 코드를 입력하면 내려가면서 실행될 줄 알았는데 그렇지 않다... case문 밖에 있는 코드는 실행되지 않는다.
swtich(x) {
case 1:
......
break;
(x가 1이 아닌 경우에도 이 부분에 입력된 코드는 실행되지 않음)
case 2:
.......
break;
}
백준 13334 철로
정렬(sort)과 우선순위큐(priority_queue)를 이용해서 풀 수 있다.
입력으로 들어온 집-사무실(사무실-집일 수도 있음, 주의) 구간을 s - e라고 하면 e를 기준으로 sorting하고 앞에서부터 보면서 주어진 범위 d만큼에 몇개가 포함되는지 체크해 나가면 되는데, 그냥 일일이 다 보면 O(N^2)이 된다.
그래서 우선순위큐(여기서 사용할 것은 최소힙)를 이용한다.
정렬된 구간을 앞에서부터 보면서 우선순위큐에도 구간의 s값을 넣는다. 그리고 우선순위 큐에서 가장 위쪽(top)에 해당하는 값을 보면서 e - d안쪽으로 들어와 있는지 보고, 포함되어 있지 않다면 우선순위 큐에서 pop한다.
범위는 d로 고정되어 있고, e의 크기대로 정렬한 상태이기 때문에,
어떤 구간이 앞쪽의 e에서 봤을 때 d만큼의 범위에 포함되지 않는다면 뒤쪽의 e에서 봐도 그 구간은 d만큼의 범위에 포함되지 않을 것이므로 빼도 되고, 해당 구간 e까지의 (범위 d만큼)포함되는 구간의 수는 그 시점에서 우선순위 큐에 들어있는 구간의 개수가 된다.
시간복잡도는 O(NlogN)이 되는 것 같다.
입력으로 들어온 집-사무실(사무실-집일 수도 있음, 주의) 구간을 s - e라고 하면 e를 기준으로 sorting하고 앞에서부터 보면서 주어진 범위 d만큼에 몇개가 포함되는지 체크해 나가면 되는데, 그냥 일일이 다 보면 O(N^2)이 된다.
그래서 우선순위큐(여기서 사용할 것은 최소힙)를 이용한다.
정렬된 구간을 앞에서부터 보면서 우선순위큐에도 구간의 s값을 넣는다. 그리고 우선순위 큐에서 가장 위쪽(top)에 해당하는 값을 보면서 e - d안쪽으로 들어와 있는지 보고, 포함되어 있지 않다면 우선순위 큐에서 pop한다.
범위는 d로 고정되어 있고, e의 크기대로 정렬한 상태이기 때문에,
어떤 구간이 앞쪽의 e에서 봤을 때 d만큼의 범위에 포함되지 않는다면 뒤쪽의 e에서 봐도 그 구간은 d만큼의 범위에 포함되지 않을 것이므로 빼도 되고, 해당 구간 e까지의 (범위 d만큼)포함되는 구간의 수는 그 시점에서 우선순위 큐에 들어있는 구간의 개수가 된다.
시간복잡도는 O(NlogN)이 되는 것 같다.
2018년 8월 2일 목요일
Codeforces Round #479(Div. 3)
C. Less or Equal
쉽게 풀 수 있을 것이라고 생각했는데, 틀려서 고민 좀 했다.
틀린 이유는 입력 조건을 제대로 확인하지 않아서 였다. (0 <= k <= n) 라는 입력 조건때문에 k값으로 0이 들어올 수도 있다.
k값이 0인 경우를 처리해주지 않아서 틀렸고, 이를 처리하여 AC를 받았다.
D. Divid by three, multiply by two
입력으로 수열이 주어지면 이전 수에 3으로 나누거나(3으로 나누어 떨어질 때 가능), 2를 곱하는 연산 둘 중의 하나를 시행하여 다음 수가 나오도록 수열을 재배치 하는데, 정답이 있다는 것이 보장된다.
나는 각 수에서 시작해보는 백트래킹 같이 재귀를 이용해 풀었는데, 같이 푼 친구는 각 수에서 시작하여 그래프를 만들어 보는 식으로(*2, /3 연산 중에 다음 수가 그 배열에 존재하는 경우에만 그래프를 만든다) 했는데, 신기하게도 그렇게 하면 한줄의 그래프가 만들어지는 것 같다. 그렇다면 애초에 어떤 수 x가 있을 때, 2x와 x/3이 둘 다 그 수열에 존재하면, 답이 나올 수 없는건가?
생각해보니 그렇다. 좀 더 정확히 말하면 어떤 수 x가 있을 때 2x를 다음 수로 하면 x/3은 그 이후에 절대 나올 수 없고, 마찬가지로 x/3을 다음수로 하면 2x는 그 이후에 절대 나올 수 없다.
1) x -> 2x가 된 경우
일단 x/3이 가능하려면 x는 3을 인수로 갖는다. 그런데 2x가 되면 인수 2가 추가 되고, x/3이 나오려면 추가된 인수 2를 없애야 하는데, 크기를 줄이는 방법은 /3밖에 없으므로 결코 x/3이 될 수 없다.(결코 x/3과 같은 인수를 가진 수가 나올 수 없다.)
2) x -> x/3이 된 경우
x는 3을 인수로 가지고 있는데 x/3은 2x에 비해 인수 3이 하나 적어지게 된다. 그런데 크기를 늘리는 방법은 *2밖에 없으므로 결코 2x가 나올 수 없다.(2x와 같은 인수를 가진 수가 나올 수 없다.)
그리고 마지막으로 출제자의 공식 풀이를 봤는데...
수열의 각 수의 인수 3의 개수를 세서 인수 3의 개수가 많은 순(내림차순)으로, 인수 3의 개수가 같으면 수의 크기가 작은 순(오름차순)으로 정렬한 후에, 그대로 수를 출력해주면 답이 된다....
엄청 간단하다... 과연 저렇게 해도 되는걸까?
생각해보면, 답이 존재한다는 게 보장되므로, 일단 3을 인수로 가지는 수가 있을 때, 우리가 할 수 있는 연산은 *2, /3뿐이므로 그 수를 만들기 위해서는 먼저 3을 인수로 가지는 수가 필요하다. 만약 인수 3의 개수가 같은 경우는 작은 쪽에 *2를 해서 만들 수 있을 것이고 개수가 다른 경우는 큰 쪽에 /3을 해서 작은 쪽을 만들 수 있을 것이다.
즉, 인수 3의 개수가 다르면 *2를 사용할 수 없고(*2를 쓰려면 인수 3의 개수가 같은 수가 존재해야 한다) /3만 가능하므로 내림차순으로 정렬하고, 인수 3의 개수가 같은 경우는 *2밖에 안되므로 오름차순으로 정렬해주면 된다.
E. Cyclic Components
일반적인 사이클이 아닌 문제 조건에 맞는 사이클을 찾는 문제인데 일반 사이클 문제보다 아주 약간 더 까다로웠다. 방문하지 않은 점부터 dfs를 해서 시작 점과 직전 점을 같이 parameter로 보내서 직전 점으로는 가지 않고, 결국 시작 점으로 돌아오면 사이클인 것으로 판단했고, 중간에 한 정점에 연결된 간선이 2개가 아니면 커트했다. 이 문제에서의 사이클은 한 정점에 간선이 2개만 연결되어 있어야 한다.
근데 이 문제 역시 공식 풀이를 보니...
일반적인 dfs를 사용하면서 vector에 한 번 dfs할 때마다 방문한 정점을 모아놓고, 그 정점들이 모두 각각 간선을 2개씩 가지고 있는지 체크해서 모두 간선을 2개씩 가지고 있으면 사이클로 본다. 하나의 정점이라도 간선이 2개가 아니라면 문제에서 요구하는 사이클이 아닐텐데, 한 번에 방문할 수 있는 모든 정점이 간선을 2개씩 가지면 문제에서 요구하는 사이클일까? 직접 그려보고 해보니 정말 dfs로 한 번에 방문 가능하면서 간선이 2개이려면 그럴 수 밖에 없다... 공부 좀 더 해서 증명도 해봐야겠다.
F. Consecutive Subsequence
이 문제는 가장 긴 증가 부분 수열 문제와 비슷해 보이는데, 1씩 증가하는 부분 수열이어야 한다. 그래서 dp로 풀 경우 일반적인 가장 긴 증가 부분 수열은 O(n^2)이 걸리는 반면에, 이 문제는 dp로 O(n)만에 풀 수 있다.
d[n] = n을 마지막으로 하는 가장 긴 1씩 증가하는 부분 수열의 길이
d[n] = d[n - 1] + 1이 된다.
일반적인 가장 긴 증가 부분 수열은 n보다 작은 모든 값에 대해 살펴봐야 해서 O(n^2)이지만, 1씩 증가하는 경우는 n - 1에 대해서만 보면되니까 O(n)이다.
물론 가장 긴 증가 부분 수열의 경우 O(nlogn)에 푸는 풀이가 있긴한데, 그 풀이도 공부해 봐야겠다.
그리고 이 문제에서는 수가 매우 커서 map(혹은 좌표압축)을 이용해 dp배열을 구현해야 한다.
쉽게 풀 수 있을 것이라고 생각했는데, 틀려서 고민 좀 했다.
틀린 이유는 입력 조건을 제대로 확인하지 않아서 였다. (0 <= k <= n) 라는 입력 조건때문에 k값으로 0이 들어올 수도 있다.
k값이 0인 경우를 처리해주지 않아서 틀렸고, 이를 처리하여 AC를 받았다.
D. Divid by three, multiply by two
입력으로 수열이 주어지면 이전 수에 3으로 나누거나(3으로 나누어 떨어질 때 가능), 2를 곱하는 연산 둘 중의 하나를 시행하여 다음 수가 나오도록 수열을 재배치 하는데, 정답이 있다는 것이 보장된다.
나는 각 수에서 시작해보는 백트래킹 같이 재귀를 이용해 풀었는데, 같이 푼 친구는 각 수에서 시작하여 그래프를 만들어 보는 식으로(*2, /3 연산 중에 다음 수가 그 배열에 존재하는 경우에만 그래프를 만든다) 했는데, 신기하게도 그렇게 하면 한줄의 그래프가 만들어지는 것 같다. 그렇다면 애초에 어떤 수 x가 있을 때, 2x와 x/3이 둘 다 그 수열에 존재하면, 답이 나올 수 없는건가?
생각해보니 그렇다. 좀 더 정확히 말하면 어떤 수 x가 있을 때 2x를 다음 수로 하면 x/3은 그 이후에 절대 나올 수 없고, 마찬가지로 x/3을 다음수로 하면 2x는 그 이후에 절대 나올 수 없다.
1) x -> 2x가 된 경우
일단 x/3이 가능하려면 x는 3을 인수로 갖는다. 그런데 2x가 되면 인수 2가 추가 되고, x/3이 나오려면 추가된 인수 2를 없애야 하는데, 크기를 줄이는 방법은 /3밖에 없으므로 결코 x/3이 될 수 없다.(결코 x/3과 같은 인수를 가진 수가 나올 수 없다.)
2) x -> x/3이 된 경우
x는 3을 인수로 가지고 있는데 x/3은 2x에 비해 인수 3이 하나 적어지게 된다. 그런데 크기를 늘리는 방법은 *2밖에 없으므로 결코 2x가 나올 수 없다.(2x와 같은 인수를 가진 수가 나올 수 없다.)
그리고 마지막으로 출제자의 공식 풀이를 봤는데...
수열의 각 수의 인수 3의 개수를 세서 인수 3의 개수가 많은 순(내림차순)으로, 인수 3의 개수가 같으면 수의 크기가 작은 순(오름차순)으로 정렬한 후에, 그대로 수를 출력해주면 답이 된다....
엄청 간단하다... 과연 저렇게 해도 되는걸까?
생각해보면, 답이 존재한다는 게 보장되므로, 일단 3을 인수로 가지는 수가 있을 때, 우리가 할 수 있는 연산은 *2, /3뿐이므로 그 수를 만들기 위해서는 먼저 3을 인수로 가지는 수가 필요하다. 만약 인수 3의 개수가 같은 경우는 작은 쪽에 *2를 해서 만들 수 있을 것이고 개수가 다른 경우는 큰 쪽에 /3을 해서 작은 쪽을 만들 수 있을 것이다.
즉, 인수 3의 개수가 다르면 *2를 사용할 수 없고(*2를 쓰려면 인수 3의 개수가 같은 수가 존재해야 한다) /3만 가능하므로 내림차순으로 정렬하고, 인수 3의 개수가 같은 경우는 *2밖에 안되므로 오름차순으로 정렬해주면 된다.
E. Cyclic Components
일반적인 사이클이 아닌 문제 조건에 맞는 사이클을 찾는 문제인데 일반 사이클 문제보다 아주 약간 더 까다로웠다. 방문하지 않은 점부터 dfs를 해서 시작 점과 직전 점을 같이 parameter로 보내서 직전 점으로는 가지 않고, 결국 시작 점으로 돌아오면 사이클인 것으로 판단했고, 중간에 한 정점에 연결된 간선이 2개가 아니면 커트했다. 이 문제에서의 사이클은 한 정점에 간선이 2개만 연결되어 있어야 한다.
근데 이 문제 역시 공식 풀이를 보니...
일반적인 dfs를 사용하면서 vector에 한 번 dfs할 때마다 방문한 정점을 모아놓고, 그 정점들이 모두 각각 간선을 2개씩 가지고 있는지 체크해서 모두 간선을 2개씩 가지고 있으면 사이클로 본다. 하나의 정점이라도 간선이 2개가 아니라면 문제에서 요구하는 사이클이 아닐텐데, 한 번에 방문할 수 있는 모든 정점이 간선을 2개씩 가지면 문제에서 요구하는 사이클일까? 직접 그려보고 해보니 정말 dfs로 한 번에 방문 가능하면서 간선이 2개이려면 그럴 수 밖에 없다... 공부 좀 더 해서 증명도 해봐야겠다.
F. Consecutive Subsequence
이 문제는 가장 긴 증가 부분 수열 문제와 비슷해 보이는데, 1씩 증가하는 부분 수열이어야 한다. 그래서 dp로 풀 경우 일반적인 가장 긴 증가 부분 수열은 O(n^2)이 걸리는 반면에, 이 문제는 dp로 O(n)만에 풀 수 있다.
d[n] = n을 마지막으로 하는 가장 긴 1씩 증가하는 부분 수열의 길이
d[n] = d[n - 1] + 1이 된다.
일반적인 가장 긴 증가 부분 수열은 n보다 작은 모든 값에 대해 살펴봐야 해서 O(n^2)이지만, 1씩 증가하는 경우는 n - 1에 대해서만 보면되니까 O(n)이다.
물론 가장 긴 증가 부분 수열의 경우 O(nlogn)에 푸는 풀이가 있긴한데, 그 풀이도 공부해 봐야겠다.
그리고 이 문제에서는 수가 매우 커서 map(혹은 좌표압축)을 이용해 dp배열을 구현해야 한다.
2018년 7월 27일 금요일
백준 14891 톱니바퀴
톱니바퀴는 0번부터 3번까지 4개가 일렬로 있고, 0 - 1 - 2 - 3 이렇게 맞닿아(-) 있다.
한 톱니바퀴 당 톱니가 0번에서 7번까지 8개가 있는데, 맞닿아 있는 톱니는 2번과 6번이다.
0번이 돌아가면 1번이 돌아간다.
1번이 돌아가면 0번과 2번이 돌아간다.
2번이 돌아가면 1번과 3번이 돌아간다.
3번이 돌아가면 2번이 돌아간다.
어떤 톱니바퀴가 돌면, 자신의 양 옆 톱니바퀴가 영향을 받아 돌아가게 하되,
회전 횟수 한 번 당, check 배열을 사용해서 한 번 돈 것은 돌지 않는 식으로 처리하면 될 것 같다.
그리고 돌리기 전 2번, 6번 톱니를 비교해서 옆의 톱니바퀴에 영향을 줄지 말지를 결정해야 한다.
영향을 주는 것이 결정되면 배열에 들어가 있는 값을 이동시켜 돌려주면 될 것 같다.
한 톱니바퀴 당 톱니가 0번에서 7번까지 8개가 있는데, 맞닿아 있는 톱니는 2번과 6번이다.
0번이 돌아가면 1번이 돌아간다.
1번이 돌아가면 0번과 2번이 돌아간다.
2번이 돌아가면 1번과 3번이 돌아간다.
3번이 돌아가면 2번이 돌아간다.
어떤 톱니바퀴가 돌면, 자신의 양 옆 톱니바퀴가 영향을 받아 돌아가게 하되,
회전 횟수 한 번 당, check 배열을 사용해서 한 번 돈 것은 돌지 않는 식으로 처리하면 될 것 같다.
그리고 돌리기 전 2번, 6번 톱니를 비교해서 옆의 톱니바퀴에 영향을 줄지 말지를 결정해야 한다.
영향을 주는 것이 결정되면 배열에 들어가 있는 값을 이동시켜 돌려주면 될 것 같다.
2018년 7월 26일 목요일
백준 1475 방 번호
내 풀이의 핵심을 설명하자면,
9를 6대신 쓸 수 있고, 6을 9 대신 쓸 수 있으므로 6과 9를 같은 숫자로 보는 것이다.
같은 숫자로 보면 한 세트에 2개씩 있으므로 (6의 개수 + 9의 개수) / 2 개만큼 필요할 것이다. 이렇게 해서 다른 숫자들의 개수와 비교를 해서 최대값을 구하면 그 값이 필요한 세트의 개수의 최소값이 된다.
*** 그런데, (6의 개수 + 9의 개수) / 2 할 때, 정수 나눗셈이기 때문에 정확히는 (6의 개수 + 9의 개수 + 1) / 2 개 만큼 필요할 것이다.
그리고 나는 숫자로 입력받아서 10으로 나누면서 한 자리씩 취하는 방법을 이용했는데, 이 경우 0이 입력으로 들어오면 count를 하지 못하므로 ans = 1로 초기화 해두는 방법을 이용했다.
2018년 7월 25일 수요일
백준 15897 (UCPC 2018 예선 H번) 잘못 구현한 에라토스테네스의 체
이 문제는 UCPC 때는 3시간 내내 붙잡고 있다가 못 푼 문제인데... 결국 풀었다.
내가 푼 방법을 정리해 보고자 한다.
----------------------------------------------
1 int n;
2 cin >> n;
3 int* sieve = new int[n + 1];
4 for(int i = 1; i <= n; i++) {
5 for(int j = 1; j <= n; j += i) {
6 sieve[j] += 1;
7 }
8 }
주어진 코드에서 6번째 줄이 입력으로 들어오는 n에 따라 몇 번 실행되는지를 구해야 하는 문제인데, 예를 들어 n이 4라고 하면
j = 1, 2, 3, 4
j = 1, 3
j = 1, 4
j = 4
이렇게 총 9번 실행된다.
바깥쪽 for문의 i 값에 따라 안쪽 for문의 실행횟수가 결정된다고 볼 수 있다.
안쪽 for문에서 j = 1부터 시작하여 i만큼 더하면 n이하일 때까지 반복하므로,
각 i마다 (n - 1) / i 만큼 안쪽 for문이 실행된다.
근데 n이 최대 10억까지 입력으로 들어오기 때문에... 일일이 다 더했다간 시간초과이다.
여러 방법을 고민해보다가 n / 2, n / 4정도까지 줄이기도 해봤었는데... 역시나 1초에 들어오기는 버겁다.
하지만 잘 생각해보면 O(루트n)만큼으로 줄일 수 있다.
내가 찾은 방법을 설명하기가 쉽지 않아서, 예를 들어서 설명해 보겠다.
n이 12인 경우를 예로 들어보면,
j = 1부터 시작하고, n번 모두 1부터 시작하므로 n번 도는 것은 무조건 확정이고,
거기에 (n - 1)을 i로 나눈 몫을 구해서 더해야 한다. 그런데, 모든 i에 대해 그 몫을 구할 필요가 없다.
숫자(a) 자신과 1만 약수로 갖는 소수를 구할 때에도 보면, 2부터 (a - 1)까지 다 나눠보고 나누어 떨어지는지(1과 자기 자신 외의 약수가 있는지)를 알아보는 방법도 있지만, 굳이 다 나누어 볼 필요 없이 (루트a) 까지만 나누어 보면된다.
12를 예로 들면
2 * 6 = 12
3 * 4 = 12
4 * 3 = 12
6 * 2 = 12
에서 볼 수 있듯이, 2, 3까지만 나누어 보면 4, 6으로 다 나누어 본 것과 같으므로...
(루트a)이하의 수로 나누면 (루트a)이상의 수로 나눠본 것과 같다는 것을 알 수 있다.
마찬가지로 이 문제에서도 똑같이는 아니지만 비슷한 개념을 적용해 볼 수 있다.
n = 12라고 하면, 먼저 1부터 시작하므로 변수 ans(답)에 12를 저장해둔다.
그리고 (n - 1)인 11을 1부터 11까지 나눈 몫을 다 더해주면 답이 되는데,
1 * 11
2 * 5
3 * 3
4 * 2
5 * 2
6 * 1
7 * 1
8 * 1
9 * 1
10 * 1
11 * 1
가 된다. 그래서 12 + 11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 41 이 답이다.
잘 보면 1 * 11 과 11 * 1, 2 * 5와 5 * 2, 가 짝을 이루고 있는 것을 볼 수 있는데,
x * x <= 11인 x = 3까지만 보면, 즉 1 * 11과 2 * 5를 보면 11 * 1과 5 * 2까지 해보지 않고
알 수 있다.
하지만, 좀 부족하다. 3 * 3은 당연히 짝이 없다해도, 4 * 2, 6 * 1, 7 * 1, ... 10 * 1 은 어떻게 예상할 수 있을까?
(루트n)까지 하는 것으로는 부족한 것이 아닐까? 다 해봐야 하지 않을까?
2 * 5로 5 * 2를 알 수 있다. 그런데 4 * 2를 알 수 있는 2 * 4는 왜 없을까? 4 * 2는 되는데 왜 2 * 4는 되지 않을까?
11 = 4 * 2 + 3 이지만 11 = 2 * 5 + 1이다. 즉 나누는 수가 2이냐 4이냐의 차이이다.
2로 나누면 나머지가 2보다 작아야 하기 때문에 몫이 크게 나온다. 4로 나누면 나머지가 4보다 작으면 되니까 몫이 2까지 나온다.
그럼 3 * 2는 어떨까? 3 * 2 + 5 = 11인데, 나머지 5가 3보다 크기 때문에 안된다.
4 * 2 + 3 = 11로 나머지 3이 4보다 작아서 가능한 것과 차이가 있다.
즉 2 * 5를 보면 5 * 2가 된다는 것은 바로 알 수 있지만, 4 * 2가 되는지, 3 * 2가 되는지는 판단하는 작업이 필요하다. 물론 이것을 일일이 확인하면 시간복잡도가 커진다.
위에서 보았듯이, x * 2가 가능하려면, n - x * 2 < x 가 되어야 한다.
여기서는 2이지만 이를 모든 경우에 적용하면
n - x * i < x 이어야 하고, 이를 정리하면, x > n / (i + 1) 이다.
즉, x * i가 가능한 x값의 하한값은 (n + i + 1) / (i + 1)이 되는 것이다.
lo = (n + i + 1) / (i + 1) 이라고 하면
lo값부터 (n - 1) / i 값까지 모두
lo * i
(lo + 1) * i
.
.
.
((n - 1) / i) * i
라는 것을 유추할 수 있는 것이니, ans += ((n - 1) / i - lo + 1) * i 를 해주면 된다.
단, 주의해야할 것은 3 * 3 같이 제곱 수들은 여러번 더해지면 안되는데, 한 번 더 더해진다.
그래서 (n - 1) / i 와 i값이 같을 때는 i만큼 빼줘야 한다.
자료형도 long long으로 하였고, 결국 이렇게 해서 AC를 받았다.
내가 푼 방법을 정리해 보고자 한다.
----------------------------------------------
1 int n;
2 cin >> n;
3 int* sieve = new int[n + 1];
4 for(int i = 1; i <= n; i++) {
5 for(int j = 1; j <= n; j += i) {
6 sieve[j] += 1;
7 }
8 }
----------------------------------------------
j = 1, 2, 3, 4
j = 1, 3
j = 1, 4
j = 4
이렇게 총 9번 실행된다.
바깥쪽 for문의 i 값에 따라 안쪽 for문의 실행횟수가 결정된다고 볼 수 있다.
안쪽 for문에서 j = 1부터 시작하여 i만큼 더하면 n이하일 때까지 반복하므로,
각 i마다 (n - 1) / i 만큼 안쪽 for문이 실행된다.
근데 n이 최대 10억까지 입력으로 들어오기 때문에... 일일이 다 더했다간 시간초과이다.
여러 방법을 고민해보다가 n / 2, n / 4정도까지 줄이기도 해봤었는데... 역시나 1초에 들어오기는 버겁다.
하지만 잘 생각해보면 O(루트n)만큼으로 줄일 수 있다.
내가 찾은 방법을 설명하기가 쉽지 않아서, 예를 들어서 설명해 보겠다.
n이 12인 경우를 예로 들어보면,
j = 1부터 시작하고, n번 모두 1부터 시작하므로 n번 도는 것은 무조건 확정이고,
거기에 (n - 1)을 i로 나눈 몫을 구해서 더해야 한다. 그런데, 모든 i에 대해 그 몫을 구할 필요가 없다.
숫자(a) 자신과 1만 약수로 갖는 소수를 구할 때에도 보면, 2부터 (a - 1)까지 다 나눠보고 나누어 떨어지는지(1과 자기 자신 외의 약수가 있는지)를 알아보는 방법도 있지만, 굳이 다 나누어 볼 필요 없이 (루트a) 까지만 나누어 보면된다.
12를 예로 들면
2 * 6 = 12
3 * 4 = 12
4 * 3 = 12
6 * 2 = 12
에서 볼 수 있듯이, 2, 3까지만 나누어 보면 4, 6으로 다 나누어 본 것과 같으므로...
(루트a)이하의 수로 나누면 (루트a)이상의 수로 나눠본 것과 같다는 것을 알 수 있다.
마찬가지로 이 문제에서도 똑같이는 아니지만 비슷한 개념을 적용해 볼 수 있다.
n = 12라고 하면, 먼저 1부터 시작하므로 변수 ans(답)에 12를 저장해둔다.
그리고 (n - 1)인 11을 1부터 11까지 나눈 몫을 다 더해주면 답이 되는데,
1 * 11
2 * 5
3 * 3
4 * 2
5 * 2
6 * 1
7 * 1
8 * 1
9 * 1
10 * 1
11 * 1
가 된다. 그래서 12 + 11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 41 이 답이다.
잘 보면 1 * 11 과 11 * 1, 2 * 5와 5 * 2, 가 짝을 이루고 있는 것을 볼 수 있는데,
x * x <= 11인 x = 3까지만 보면, 즉 1 * 11과 2 * 5를 보면 11 * 1과 5 * 2까지 해보지 않고
알 수 있다.
하지만, 좀 부족하다. 3 * 3은 당연히 짝이 없다해도, 4 * 2, 6 * 1, 7 * 1, ... 10 * 1 은 어떻게 예상할 수 있을까?
(루트n)까지 하는 것으로는 부족한 것이 아닐까? 다 해봐야 하지 않을까?
2 * 5로 5 * 2를 알 수 있다. 그런데 4 * 2를 알 수 있는 2 * 4는 왜 없을까? 4 * 2는 되는데 왜 2 * 4는 되지 않을까?
11 = 4 * 2 + 3 이지만 11 = 2 * 5 + 1이다. 즉 나누는 수가 2이냐 4이냐의 차이이다.
2로 나누면 나머지가 2보다 작아야 하기 때문에 몫이 크게 나온다. 4로 나누면 나머지가 4보다 작으면 되니까 몫이 2까지 나온다.
그럼 3 * 2는 어떨까? 3 * 2 + 5 = 11인데, 나머지 5가 3보다 크기 때문에 안된다.
4 * 2 + 3 = 11로 나머지 3이 4보다 작아서 가능한 것과 차이가 있다.
즉 2 * 5를 보면 5 * 2가 된다는 것은 바로 알 수 있지만, 4 * 2가 되는지, 3 * 2가 되는지는 판단하는 작업이 필요하다. 물론 이것을 일일이 확인하면 시간복잡도가 커진다.
위에서 보았듯이, x * 2가 가능하려면, n - x * 2 < x 가 되어야 한다.
여기서는 2이지만 이를 모든 경우에 적용하면
n - x * i < x 이어야 하고, 이를 정리하면, x > n / (i + 1) 이다.
즉, x * i가 가능한 x값의 하한값은 (n + i + 1) / (i + 1)이 되는 것이다.
lo = (n + i + 1) / (i + 1) 이라고 하면
lo값부터 (n - 1) / i 값까지 모두
lo * i
(lo + 1) * i
.
.
.
((n - 1) / i) * i
라는 것을 유추할 수 있는 것이니, ans += ((n - 1) / i - lo + 1) * i 를 해주면 된다.
단, 주의해야할 것은 3 * 3 같이 제곱 수들은 여러번 더해지면 안되는데, 한 번 더 더해진다.
그래서 (n - 1) / i 와 i값이 같을 때는 i만큼 빼줘야 한다.
자료형도 long long으로 하였고, 결국 이렇게 해서 AC를 받았다.
2018년 7월 21일 토요일
백준 10803 정사각형 만들기
엄청 어려워 보였는데, 생각해보니 간단할 것 같기도 하다.
문제 조건을 보면 한 번 짜르면 무조건 끝까지 잘라야 하고, 수평/ 수직으로만 자를 수 있기 때문에...
d[n][m] = n * m의 직사각형을 잘라서 얻을 수 있는 정사각형 조각의 최소 개수
로 놓고, 수평으로 자르는 경우, 수직으로 자르는 경우 1 ~ n, 1 ~ m 모든 경우를 다 보면서 그 중 최소값을 얻어내면 될 것 같고,
최소값을 구해야 하므로 n == m인 경우 더 자를 필요 없이 1을 리턴해주는 식으로 구현하면 될 것 같다.
그런데, 생각해보니 그렇게 하면 시간 복잡도가 n * m * (n + m)이 될 것 같은데...
100억 정도가 되어 너무 크다. 그런데 생각해보면 n + m부분에서 n + m을 다 해볼 필요 없이, 그러니까 1 ~ n, 1 ~ m을 다 볼 필요 없이 절반까지만 보면 될 것 같다. 어차피 절반 이후로는 똑같으니까...
음... 그래도 여전히 시간복잡도가 크다. 그런데 위와 같이 절반까지만 보기 때문에 재귀로 구현하면 d[n][m]에 해당하는 n * m부분이 정말 n * m만큼 호출될 것 같지는 않다.... 일단 구현해 봐야겠다.
제출했더니 역시나 시간초과가 떴다...
어떻게 줄여야할까?
음 일단 생각나는 것이... d[w][h] 나 d[h][w]나 같다는 것이다. 이것을 한 번 적용해 봐야겠다. 그러면 또 반 정도 줄일 수 있을 거 같긴하다.
음 그런데, 저것을 적용하니 좀 답이 잘못 나온다.(10000, 100인 경우에...)
왜 그런지 이유는 잘 모르겠지만... -> 생각해보니 애초에 dp배열크기가 d[10001][101]이라 그런 것 같다. w와 h의 범위가 다르다... 그래서 배열 범위를 초과하여 잘못된 값이 들어간 것 같다.
일단 또 생각해본 것이 w나 h 둘 중 하나가 1인 경우 굳이 더 나눠 볼 필요가 없다는 것이다. 일단 이 부분을 추가해도 시간이 그리 단축되지는 않는다.
확실하지는 않은데, w와 h의 gcd(최대공약수)값부터 자르거나 최대공약수 단위로 자르는 건 어떨까? 최대공약수가 1이면 1부터 해야겠지만, 최대공약수가 2이기만 해도 엄청 많이 줄일 수 있을 것 같은데...
확실하게 증명은 할 수 없지만... 일단 최대공약수부터 시작해서 최대공약수 단위로 자르는 식으로 구현해 봐야겠다.
일단 예제에 대해서는 제대로 나오기는 하는데, 시간초과를 받았다... 9999 100 같은 케이스에 대해서는 여전히 느리다.
2018년 7월 20일 금요일
백준 15685 드래곤 커브
일단 규칙을 좀 생각해봤다.
1. k세대는 (k - 1)세대를 시계방향으로 90도 돌린 후에 (k - 1)세대의 끝점에 90도 돌린 것의 끝점을 붙이게 된다. 그래서 (k - 1)세대의 역방향으로 새로운 길이 추가된다고 볼 수 있다.
역방향은 x, y방향은 각각 유지하면서 부호만 바꿔주면 된다.
2. 그리고 시계방향으로 90도 돌릴 경우 각 이동 규칙은...
y방향 음수 -> x방향 양수
y방향 양수 -> x방향 음수
x방향 음수 -> y방향 음수
x방향 양수 -> y방향 양수
일단 x -> y, y -> x 가 되고, y방향의 경우만 부호가 바뀐다.
(x, y) -> (-y, x) 로 해주면 된다.
규칙 1과 2를 이용해서 점을 찍고나서
모든 점을 돌면서 각 점마다 오른쪽, 아래 방향으로 1 * 1 정사각형을 구성하는 꼭지점이 있는지 확인해 보면서 1 * 1 정사각형의 개수를 세면될 것 같다.
규칙 1과 2를 이용해서 점을 찍는 부분의 구현이 좀 까다롭다.
먼저 k세대를 구하기 위해서 0세대부터 시작을 한다.
i세대의 이동 방향을 reverse해주고, 그 값을 90도 돌려주는 작업을 해준다.
그리고 i세대의 끝에 이어 붙인다. 그러면 (i+1)세대의 이동방향이 완성된다. 각 이동 방향은 pair(x, y)로 묶어서 vector에 이어붙일 것이다.
이렇게 k세대의 이동방향을 구하면 그를 토대로 점을 check해준다.
결국 이렇게 구현해서 AC를 받았다.
코드가 꽤 길어졌는데, 맞은 사람을 보니 짧게 구현한 사람도 꽤 있다. 이해는 잘 안 가지만, 좀 더 간단히 구현할 수 있는 방법이 있는 것 같다... 더 열심히 해야겠다.
1. k세대는 (k - 1)세대를 시계방향으로 90도 돌린 후에 (k - 1)세대의 끝점에 90도 돌린 것의 끝점을 붙이게 된다. 그래서 (k - 1)세대의 역방향으로 새로운 길이 추가된다고 볼 수 있다.
역방향은 x, y방향은 각각 유지하면서 부호만 바꿔주면 된다.
2. 그리고 시계방향으로 90도 돌릴 경우 각 이동 규칙은...
y방향 음수 -> x방향 양수
y방향 양수 -> x방향 음수
x방향 음수 -> y방향 음수
x방향 양수 -> y방향 양수
일단 x -> y, y -> x 가 되고, y방향의 경우만 부호가 바뀐다.
(x, y) -> (-y, x) 로 해주면 된다.
규칙 1과 2를 이용해서 점을 찍고나서
모든 점을 돌면서 각 점마다 오른쪽, 아래 방향으로 1 * 1 정사각형을 구성하는 꼭지점이 있는지 확인해 보면서 1 * 1 정사각형의 개수를 세면될 것 같다.
규칙 1과 2를 이용해서 점을 찍는 부분의 구현이 좀 까다롭다.
먼저 k세대를 구하기 위해서 0세대부터 시작을 한다.
i세대의 이동 방향을 reverse해주고, 그 값을 90도 돌려주는 작업을 해준다.
그리고 i세대의 끝에 이어 붙인다. 그러면 (i+1)세대의 이동방향이 완성된다. 각 이동 방향은 pair(x, y)로 묶어서 vector에 이어붙일 것이다.
이렇게 k세대의 이동방향을 구하면 그를 토대로 점을 check해준다.
결국 이렇게 구현해서 AC를 받았다.
코드가 꽤 길어졌는데, 맞은 사람을 보니 짧게 구현한 사람도 꽤 있다. 이해는 잘 안 가지만, 좀 더 간단히 구현할 수 있는 방법이 있는 것 같다... 더 열심히 해야겠다.
백준 1005 ACM Craft
먼저 주어진 건설 순서를 이용해서 그래프를 만들고, 지어야 할 건물 W부터 시작해서 거꾸로 탐색하는 방식으로 dp로 구현해 볼 생각이다.
거꾸로 탐색하면서 건물 W를 짓기 전에 지어야 할 각 건물까지의 시간 중 최대값을 선택하는 방식으로 하면 될 것 같다. 그리고 이미 탐색한 부분은 메모이제이션을 통해 더 탐색하지 않도록 한다.
위상정렬 문제를 예전에 푼 것을 좀 찾아봐서 다시 풀어봐야겠다.
이 문제는 그냥 그래프 + dp처럼 풀어서 AC를 받았는데, 예전에 풀었던 문제 중에 경로까지 출력해야 하는 문제가 있어서 좀 까다로웠던 것 같고 위상정렬을 풀기 위한 방식이 있었는데... 기억이 잘 안난다. 찾아서 풀어보자!
거꾸로 탐색하면서 건물 W를 짓기 전에 지어야 할 각 건물까지의 시간 중 최대값을 선택하는 방식으로 하면 될 것 같다. 그리고 이미 탐색한 부분은 메모이제이션을 통해 더 탐색하지 않도록 한다.
위상정렬 문제를 예전에 푼 것을 좀 찾아봐서 다시 풀어봐야겠다.
이 문제는 그냥 그래프 + dp처럼 풀어서 AC를 받았는데, 예전에 풀었던 문제 중에 경로까지 출력해야 하는 문제가 있어서 좀 까다로웠던 것 같고 위상정렬을 풀기 위한 방식이 있었는데... 기억이 잘 안난다. 찾아서 풀어보자!
2018년 7월 19일 목요일
CS Academy Round 84 Three ones
koosaga님이 출제하신다고 슬랙에 홍보해 주셔서 CS Academy를 처음 알게되었고, round 84에 참여해 봤는데, 일단 한 문제밖에 못 풀었다...
그 외 다른 문제는 읽지도 못했고, Three ones문제는 좀 고민을 했는데...
일단 상세한 풀이는 없지만 소스코드가 있어서 여기 기록해 둔다. 생각해보고 내가 풀이를 정리해 봐야겠다.
문제
https://csacademy.com/contest/round-84/task/three-ones/
풀이
https://csacademy.com/contest/round-84/analysis/
그 외 다른 문제는 읽지도 못했고, Three ones문제는 좀 고민을 했는데...
일단 상세한 풀이는 없지만 소스코드가 있어서 여기 기록해 둔다. 생각해보고 내가 풀이를 정리해 봐야겠다.
문제
https://csacademy.com/contest/round-84/task/three-ones/
풀이
https://csacademy.com/contest/round-84/analysis/
STL queue에서 pop에 리턴값이 없는 이유
백준 슬랙에서 누군가 왜 STL queue에서 pop을 쓰면 pop만되고, pop된 값이 리턴되지 않는지 질문했는데, 그에 대한 답으로 아래의 링크를 올려주셨다.
https://stackoverflow.com/questions/25035691/why-doesnt-stdqueuepop-return-value
읽어봤는데, 영어라 확실히 이해한 것 같지는 않지만...
내가 이해한 것을 정리해보면,
"pop을 쓸 때, queue에 있는 해당 값을 제거하게 되기 때문에 해당 값을 리턴해주기 위해서는 해당 값의 참조값(주소값)을 이용해 리턴해줄 수 없고, 따로 값을 저장하고 리턴해야 하는 return by value를 사용해야 하고 이는 비효율적이다. "
라는 의견도 있었고,
하지만 진짜 이유는... 만약 해당 값을 리턴하게 된다면, 리턴하기 전에 해당 엘리먼트를 지워야하기 때문에, 이미 어디에도 존재하지 않는 값을 리턴하는 것이라... exception으로부터 안전하지 못하기 때문에... exception safety를 위해서라고 한다.
사실 정확히 이해는 안 되었지만, exception부분은 C++과 STL에 대해서 좀 공부를 해야 이해할 수 있을 것 같다. C++에 대해서 공부해보고 다시 생각해 봐야겠다.
https://stackoverflow.com/questions/25035691/why-doesnt-stdqueuepop-return-value
읽어봤는데, 영어라 확실히 이해한 것 같지는 않지만...
내가 이해한 것을 정리해보면,
"pop을 쓸 때, queue에 있는 해당 값을 제거하게 되기 때문에 해당 값을 리턴해주기 위해서는 해당 값의 참조값(주소값)을 이용해 리턴해줄 수 없고, 따로 값을 저장하고 리턴해야 하는 return by value를 사용해야 하고 이는 비효율적이다. "
라는 의견도 있었고,
하지만 진짜 이유는... 만약 해당 값을 리턴하게 된다면, 리턴하기 전에 해당 엘리먼트를 지워야하기 때문에, 이미 어디에도 존재하지 않는 값을 리턴하는 것이라... exception으로부터 안전하지 못하기 때문에... exception safety를 위해서라고 한다.
사실 정확히 이해는 안 되었지만, exception부분은 C++과 STL에 대해서 좀 공부를 해야 이해할 수 있을 것 같다. C++에 대해서 공부해보고 다시 생각해 봐야겠다.
백준 2091 동전
이 문제는 꽤 오래전부터 못 풀던 문제인데, 인터넷에 검색해서 공식 사이트의 풀이를 찾았다.
물론 코드만 있어서 좀 분석이 필요하다. 시간이 좀 걸릴 것 같지만 틈틈이 계속 봐야겠다.
https://contest.felk.cvut.cz/03prg/solved/change.c
물론 코드만 있어서 좀 분석이 필요하다. 시간이 좀 걸릴 것 같지만 틈틈이 계속 봐야겠다.
https://contest.felk.cvut.cz/03prg/solved/change.c
/*
* Solution to Charlie's change task
*/
#include <stdio.h>
const int p[4] = {1,5,10,25};
#define MIN(a,b) ((a) < (b) ? (a) : (b))
int compute(int *c, int *use, int start, int price)
{
int i, val;
val = 0;
for (i = 0; i <= start; i++)
val += c[i]*p[i];
for (i = start; i >= 0; i--) {
val -= p[i]*c[i];
if (val > price)
use[i] = 0;
else
use[i] = (price-val+p[i]-1)/p[i];
if (use[i] > c[i] || use[i]*p[i] > price)
return -1;
price -= use[i]*p[i];
}
val = 0;
for (i = 0; i < 4; i++)
val += use[i];
return val;
}
int main(void)
{
int price, c[4], val, use[2][4], i, coins[2];
while (1) {
scanf("%d %d %d %d %d", &price, &c[0], &c[1], &c[2], &c[3]);
if (!price && !c[0] && !c[1] && !c[2] && !c[3])
break;
val = 0;
for (i = 0; i < 3; i++)
val += c[i]*p[i];
if (val > price)
use[0][3] = 0;
else
use[0][3] = MIN((price-val+p[3]-1)/p[3], c[3]);
coins[0] = compute(c, use[0], 2, price - use[0][3]*p[3]);
if (use[0][3] < c[3]) {
use[1][3] = use[0][3]+1;
coins[1] = compute(c, use[1], 2, price - use[1][3]*p[3]);
}
else
coins[1] = -1;
if (coins[0] == -1 && coins[1] == -1)
puts("Charlie cannot buy coffee.");
else {
i = 0;
if (coins[1] > coins[0])
i = 1;
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", use[i][0], use[i][1], use[i][2], use[i][3]);
}
}
return 0;
}
백준 2751 수 정렬하기 2
이 문제를 풀 때 두 가지 방법으로 풀어보았다.
1. C++ STL의 sort사용
2. bucket sort 사용
시간 복잡도는 각각 O(NlogN), O(N)으로 차이가 많이 나지만,
실제 백준 온라인 저지에 제출했을 때, 8ms정도 밖에 차이가 나지 않는다. 왜 그럴까?
일단 스타트링크 오프라인 강의 질문 사이트를 통해 백준님께 질문을 남겼다.
1. C++ STL의 sort사용
2. bucket sort 사용
시간 복잡도는 각각 O(NlogN), O(N)으로 차이가 많이 나지만,
실제 백준 온라인 저지에 제출했을 때, 8ms정도 밖에 차이가 나지 않는다. 왜 그럴까?
일단 스타트링크 오프라인 강의 질문 사이트를 통해 백준님께 질문을 남겼다.
백준 11004 k번째 수 구현 관련...
일단 cin, cout을 쓸 때, ios_base::sync_with_stdio(false); 를 써주지 않으면 시간초과를 받을 수 있다.
그리고 이전과 달리 STL sort를 사용해도 통과하느 것으로 보인다.
아무튼 quick sort를 응요한 quick selection을 이용해서 구현했는데...
맨 왼쪽 수를 pivot으로 정하고, pivot의 위치를 찾아내는 partition함수의 구현에서,
코드 1)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;
while(lo < hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;
while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;
if(lo < hi) swapArr(lo, hi);
}
swapArr(hi, pivot);
return hi;
}
---------------------------------------------------------------------------------------------------
위의 코드와 같이 구현했다가, 틀렸는데 ,
아래 코드 2) 와 같이 구현하면
코드 2)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;
while(lo <= hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;
while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;
if(lo < hi) swapArr(lo, hi);
}
swapArr(hi, pivot);
return hi;
}
---------------------------------------------------------------------------------------------------
맞았습니다를 받을 수 있다.
달라진 점은 while(lo < hi) -> while(lo <= hi) 이다. 사실 처음에는 lo 와 hi가 같아질 일도 없고, 설령 같아지더라도 그 때 while문을 나오는 것이 문제될 일은 없다고 생각했다. 그런데 잘 생각해보니 길이가 2인 수열이 있으면 lo와 hi가 2로 같아져 아예 while문 안으로 들어갈 수 없게되는 문제가 있다.
그렇게 되면 예를 들어 {1, 2}라는 수열이 있을 때 hi값은 2가되어 while문 안에 못 들어가고, swapArr(hi, pivot)을 거쳐 {2, 1}로 수열을 변경하게 되어 잚못된 답이 나오게 된다.
그리고 이전과 달리 STL sort를 사용해도 통과하느 것으로 보인다.
아무튼 quick sort를 응요한 quick selection을 이용해서 구현했는데...
맨 왼쪽 수를 pivot으로 정하고, pivot의 위치를 찾아내는 partition함수의 구현에서,
코드 1)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;
while(lo < hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;
while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;
if(lo < hi) swapArr(lo, hi);
}
swapArr(hi, pivot);
return hi;
}
---------------------------------------------------------------------------------------------------
위의 코드와 같이 구현했다가, 틀렸는데 ,
아래 코드 2) 와 같이 구현하면
코드 2)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;
while(lo <= hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;
while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;
if(lo < hi) swapArr(lo, hi);
}
swapArr(hi, pivot);
return hi;
}
---------------------------------------------------------------------------------------------------
맞았습니다를 받을 수 있다.
달라진 점은 while(lo < hi) -> while(lo <= hi) 이다. 사실 처음에는 lo 와 hi가 같아질 일도 없고, 설령 같아지더라도 그 때 while문을 나오는 것이 문제될 일은 없다고 생각했다. 그런데 잘 생각해보니 길이가 2인 수열이 있으면 lo와 hi가 2로 같아져 아예 while문 안으로 들어갈 수 없게되는 문제가 있다.
그렇게 되면 예를 들어 {1, 2}라는 수열이 있을 때 hi값은 2가되어 while문 안에 못 들어가고, swapArr(hi, pivot)을 거쳐 {2, 1}로 수열을 변경하게 되어 잚못된 답이 나오게 된다.
2018년 7월 17일 화요일
ios_base::sync_with_stdio(false)
cin, cout을 빠르게 쓰려고 ios_base::sync_with_stdio(false)을 main함수 위쪽에 썼는데, 컴파일 과정에서 에러가 나서 main함수 안에 넣어주었고, 그렇게 하니 에러가 나지 않았다.
추가) < 10989 수 정렬하기 3 >을 풀면서 cin, cout도 써보고 scanf, printf도 써보면서 테스트해 봤는데, ios_base::sync_with_stdio(false)를 써주면 그냥 scanf, printf을 사용했을 때 보다 cin, cout을 사용했을 때, 더 빠른 것을 알 수 있었다.
추가) < 10989 수 정렬하기 3 >을 풀면서 cin, cout도 써보고 scanf, printf도 써보면서 테스트해 봤는데, ios_base::sync_with_stdio(false)를 써주면 그냥 scanf, printf을 사용했을 때 보다 cin, cout을 사용했을 때, 더 빠른 것을 알 수 있었다.
백준 10814 나이순 정렬
나이와 가입 순서를 가지고 sorting하여 문제를 풀었는데, 과거에 내가 푼 방법을 보니 꽤 괜찮은 방법이 있어 여기에 기록한다.
나이가 1 ~ 200이므로 크기 201의 vector<string>배열을 만든다.
나이를 입력 받으면 radix sort(bucket sort)처럼 나이를 vector배열의 index로 사용하여 vector배열에 이름(string)을 저정한다.
나이 순으로 정렬하고, 나이가 같으면 가입순서대로 정렬해야 하는데, 일단 나이를 배열의 index로 사용했으므로 1부터 200까지 보면 나이순으로는 정렬이 되어 있고, 각 나이에 해당되는 배열에 가입한 순서대로 string이 저장되어 있으므로 따로 가입 순서에 따라 정렬할 필요도 없다.
그냥 배열의 순서대로 배열 내 저장된 순서대로 출력하면 정답이 된다.
나이가 1 ~ 200이므로 크기 201의 vector<string>배열을 만든다.
나이를 입력 받으면 radix sort(bucket sort)처럼 나이를 vector배열의 index로 사용하여 vector배열에 이름(string)을 저정한다.
나이 순으로 정렬하고, 나이가 같으면 가입순서대로 정렬해야 하는데, 일단 나이를 배열의 index로 사용했으므로 1부터 200까지 보면 나이순으로는 정렬이 되어 있고, 각 나이에 해당되는 배열에 가입한 순서대로 string이 저장되어 있으므로 따로 가입 순서에 따라 정렬할 필요도 없다.
그냥 배열의 순서대로 배열 내 저장된 순서대로 출력하면 정답이 된다.
2018년 7월 11일 수요일
#define의 속도에 대해...
https://algospot.com/forum/read/3568/
위의 링크와 캡쳐에서 볼 수 있듯이, #define을 쓰면 함수가 여러번 호출될 수 있어 더 느려질 수 있다.
그리고 전처리기 등...에 대해 공부할 필요가 있다. CS공부하자...!
위의 링크와 캡쳐에서 볼 수 있듯이, #define을 쓰면 함수가 여러번 호출될 수 있어 더 느려질 수 있다.
그리고 전처리기 등...에 대해 공부할 필요가 있다. CS공부하자...!
2018년 7월 9일 월요일
백준 2225 합분해
거의 같은 로직의 코드를 제출했는데 속도가 12ms, 32ms로 매우 다르게 나와서 무슨 차이인가 하고 봤더니... MOD값을 const로 선언했냐 안 했냐의 차이였다..
const로 선언해주니 무려 20ms나 줄어들었다.
for문 안에서 매번 modular 연산을 해주는데
const로 선언하면 상수처럼 되어 속도가 좀 더 빨라지나보다... 나중에 그 이유에 대해 좀 더 자세히 알아보자.
2018년 7월 8일 일요일
백준 2156 포도주 시식
d[i][x] = i번째 잔부터 연속 x잔을 마실 때, 최대로 마실 수 있는 포도주의 양
d[i][0] = max(d[i + 1][1], d[i + 1][2])
d[i][1] = d[i + 1][0] + wine[i]
d[i][2] = d[i + 2][0] + wine[i] + wine[i + 1]
이렇게 풀었는데, 틀렸다...
감사하게도 질문게시판에 반례를 올려주신 분이 있었다.
https://www.acmicpc.net/board/view/21703#comment-37134
8
7 7 0 5 7 7 0 3
d[i][0] = max(d[i + 1][1], d[i + 1][2]) -> 이 부분이 문제였다.
나는 i번째 포도주를 안 마시기로 했으면, 그 다음 포도주는 무조건 마셔야 최대값이 된다고 생각했는데, 이 것은 맨 앞인 경우만 해당된다. 맨 앞의 2개의 잔을 모두 안 마시면 최대가 아니기 때문에(맨 앞의 1개의 잔을 마시면 그게 더 크므로) 이렇게 생각했었는데, 중간 부분에서는 가운데 2개가 비어야 최대가 될 수 있는 경우도 있다.
예를 들면, o o x x o o 인 경우... 가운데 x x중 하나를 선택하게 되면 3잔 연속이 되니까, o를 하나 포기해야 한다. 이 때, x에 있는 값이 o에 있는 값보다 작으면 최대가 될 수 없다. 그래서 최대가 되기 위해 x x -> 이 부분을 선택하지 않아야 할 수 있다.
그래서
d[i][0] = max(d[i + 1][1], d[i + 1][2])
-> d[i][0] = max(d[i + 1][0], max(d[i + 1][1], d[i + 1][2])) 으로 수정하였고, AC를 받았다.
d[i][0] = max(d[i + 1][1], d[i + 1][2])
d[i][1] = d[i + 1][0] + wine[i]
d[i][2] = d[i + 2][0] + wine[i] + wine[i + 1]
이렇게 풀었는데, 틀렸다...
감사하게도 질문게시판에 반례를 올려주신 분이 있었다.
https://www.acmicpc.net/board/view/21703#comment-37134
8
7 7 0 5 7 7 0 3
나는 i번째 포도주를 안 마시기로 했으면, 그 다음 포도주는 무조건 마셔야 최대값이 된다고 생각했는데, 이 것은 맨 앞인 경우만 해당된다. 맨 앞의 2개의 잔을 모두 안 마시면 최대가 아니기 때문에(맨 앞의 1개의 잔을 마시면 그게 더 크므로) 이렇게 생각했었는데, 중간 부분에서는 가운데 2개가 비어야 최대가 될 수 있는 경우도 있다.
예를 들면, o o x x o o 인 경우... 가운데 x x중 하나를 선택하게 되면 3잔 연속이 되니까, o를 하나 포기해야 한다. 이 때, x에 있는 값이 o에 있는 값보다 작으면 최대가 될 수 없다. 그래서 최대가 되기 위해 x x -> 이 부분을 선택하지 않아야 할 수 있다.
그래서
-> d[i][0] = max(d[i + 1][0], max(d[i + 1][1], d[i + 1][2])) 으로 수정하였고, AC를 받았다.
2018년 7월 6일 금요일
백준 1463 1로 만들기
일단 3으로, 2로 모두 나누어 떨어지면 3으로 나누는 것이 최소값을 구할 수 있는 방법일까? 2로 나눠야 최소값이 나오는 경우도 있지 않을까?
그리고 3으로 나누어 떨어지는 홀수를 3으로 바로 안 나누고 1을 뺀 후에 2로 나누는 경우가 3으로 바로 나누는 경우보다 나을 수도 있지 않을까?
위의 사항들에 대해서... 확실하게 어떤 것이 최적이다라고 증명을 할 수 있으려나...
일단 증명을 안 한다면 모든 경우를 다 해보는 방식으로 dp를 적용해서 풀어도 된다.
-------------------------------------------------------
1. x가 3으로 나누어 떨어지면 3으로 나눈다.
2. x가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.
d[n] = 정수 n에 세가지의 연산을 적절히 사용해서 1을 만들기 위해 연산을 사용하는 횟수의 최소값.
d[n] = min(d[n / 3], d[n / 2], d[n - 1]) + 1;
그리고 3으로 나누어 떨어지는 홀수를 3으로 바로 안 나누고 1을 뺀 후에 2로 나누는 경우가 3으로 바로 나누는 경우보다 나을 수도 있지 않을까?
위의 사항들에 대해서... 확실하게 어떤 것이 최적이다라고 증명을 할 수 있으려나...
일단 증명을 안 한다면 모든 경우를 다 해보는 방식으로 dp를 적용해서 풀어도 된다.
-------------------------------------------------------
1. x가 3으로 나누어 떨어지면 3으로 나눈다.
2. x가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.
d[n] = 정수 n에 세가지의 연산을 적절히 사용해서 1을 만들기 위해 연산을 사용하는 횟수의 최소값.
d[n] = min(d[n / 3], d[n / 2], d[n - 1]) + 1;
2018년 7월 5일 목요일
10820 문자열 분석, fgets 주의사항
fgets로 받는 경우 입력 문자열의 최대길이가 100이므로 개행('\n')과 NULL값까지 고려해서 char 배열을 102로 잡아줘야 한다. str[102]
그런데 틀려서 보니...
fgets(str, 100, stdin)에서... fgets를 쓰면 개행('\n')까지 받기 때문에, 최대 100자까지가 아닌 101자까지 받도록 해야 한다...
fgets(str, 101, stdin);
아 그런데 또 틀렸다...
직접 테스트 해보니.. fgets(str, 11, stdin)으로 할 경우 10글자까지만 저장된다. 개행('\n')도 저장되지 않고 딱 10글자만 저장된다. (개행까지 저장되려면 9글자를 입력해야 한다.)
결국 저 11이라는 숫자는 문자열의 NULL값까지 포함한 길이인 것 같다.
그렇기 때문에 fgets(str, 102, stdin)으로 해줘야 통과할 수 있을 것 같다.
그렇게 고쳐서 제출했더니 AC를 받았다....
그런데 틀려서 보니...
fgets(str, 100, stdin)에서... fgets를 쓰면 개행('\n')까지 받기 때문에, 최대 100자까지가 아닌 101자까지 받도록 해야 한다...
fgets(str, 101, stdin);
아 그런데 또 틀렸다...
직접 테스트 해보니.. fgets(str, 11, stdin)으로 할 경우 10글자까지만 저장된다. 개행('\n')도 저장되지 않고 딱 10글자만 저장된다. (개행까지 저장되려면 9글자를 입력해야 한다.)
결국 저 11이라는 숫자는 문자열의 NULL값까지 포함한 길이인 것 같다.
그렇기 때문에 fgets(str, 102, stdin)으로 해줘야 통과할 수 있을 것 같다.
그렇게 고쳐서 제출했더니 AC를 받았다....
2018년 7월 2일 월요일
백준 1008 A/B
https://www.acmicpc.net/board/view/2432
정답과의 차이가 1e-9이하이면 정답인 문제
출력되는 소수의 범위를 늘려야 한다.
float로 하면 6자리정도까지만 정확하기 때문에 틀리게 된다.
double(%lf)를 이용해야 한다.
정답과의 차이가 1e-9이하이면 정답인 문제
출력되는 소수의 범위를 늘려야 한다.
float로 하면 6자리정도까지만 정확하기 때문에 틀리게 된다.
double(%lf)를 이용해야 한다.
백준 1002 터렛
주의사항
(x1, y1)과 (x2, y2)가 같은 경우도 생각해야 함!
원 하나가 다른 원 하나를 포함하는 경우도 생각해야 함. 포함하여 접점이 1개일 수도 있고, 포함해서 접점이 없을 수도 있다.
근데 이 모든 것을 간단하게 처리하는 방법도 있다.
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void) {
int t;
scanf("%d", &t);
while(t--) {
double x1, y1, x2, y2;
double dist[3];
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &dist[0], &x2, &y2, &dist[1]);
dist[2]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
sort(dist, dist+3);
if(dist[0]==0 && dist[1]==dist[2]) {
printf("-1\n");
}
else if(dist[2]>dist[1]+dist[0]) {
printf("0\n");
}
else if(dist[2]==dist[1]+dist[0]) {
printf("1\n");
}
else {
printf("2\n");
}
}
return 0;
}
(x1, y1)과 (x2, y2)가 같은 경우도 생각해야 함!
원 하나가 다른 원 하나를 포함하는 경우도 생각해야 함. 포함하여 접점이 1개일 수도 있고, 포함해서 접점이 없을 수도 있다.
근데 이 모든 것을 간단하게 처리하는 방법도 있다.
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void) {
int t;
scanf("%d", &t);
while(t--) {
double x1, y1, x2, y2;
double dist[3];
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &dist[0], &x2, &y2, &dist[1]);
dist[2]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
sort(dist, dist+3);
if(dist[0]==0 && dist[1]==dist[2]) {
printf("-1\n");
}
else if(dist[2]>dist[1]+dist[0]) {
printf("0\n");
}
else if(dist[2]==dist[1]+dist[0]) {
printf("1\n");
}
else {
printf("2\n");
}
}
return 0;
}
2018년 4월 10일 화요일
13458 시험 감독 풀이
이 문제에서 주의해야 할 점 (코드의 주석 참조)
1. 총감독관은 반드시 1명 있어야 한다. (없어도 안되고, 2명 이상이 있어도 안된다.)
2. 부감독관은 있어도 되고 없어도 된다.
3. 최악의 경우(N: 1,000,000 , Ai가 모두 1,000,000, B: 1, C: 1 인 경우) 필요한 감독관의 수가 1,000,000 * 1,000,000 명이 될 수 있으므로 int형 변수를 이용해 결과를 출력할 경우 틀리게 된다.
풀이
먼저 총감독관은 각 방마다 무조건 1명씩 있어야 하므로 N명이 필요하다.
이제 각 방에서 감시해야할 응시자 수는 Ai - B 가 된다.
나머지 시험 응시자들은 부감독관들이 모두 감시해야 한다.
각 방의 (Ai - B) 값을 "부감독관이 감시할 수 있는 응시자 수"로 나누어 주면,
각 방에 남은 응시자들을 모두 감시하기 위해 필요한 부감독관의 수를 구할 수 있다.
단, 이 때 나누어 떨어지는 경우는 괜찮지만 그렇지 않는 경우에 1을 더해줘야 하는 번거로움이 있는데, 이 부분은 C - 1을 더해서 나누어 줌으로써 편하게 계산할 수 있다.
코드
#include <cstdio>
// long long을 편하게 사용하기 위해 llint로 설정
typedef long long llint;
// N(시험장의 수),
// B(총 감독관이 한 방에서 감시할 수 있는 응시자의 수),
// C(부감독관이 한 방에서 감시할 수 있는 응시자의 수)
int n, b, c;
// 각 시험장에 있는 응시자의 수를 저장할 배열
int a[1000000];
// 정답을 저장할 변수(필요한 감독관 수의 최소값, long long 형)
llint ans = 0;
int main() {
// 시험장(방)의 개수를 입력받는다.
scanf("%d", &n);
// 각 방에 있는 응시자 수를 입력받는다.
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// 한 방에서 감시할 수 있는 응시자 수를 입력 받는다.(총감독관, 부감독관)
scanf("%d %d", &b, &c);
// (1) 총감독관
// 총 감독관이 감시할 수 있는 응시자 수를 뺀다.
// 뺄 때, 음수가 되지 않도록 조건이 필요하다.
for(int i = 0; i < n; i++) {
if(a[i] >= b)
a[i] -= b;
else //(방의 인원 < 감시할 수 있는 응시자수)인 경우
a[i] = 0;
}
// 총감독관은 반드시 각 방에 1명씩 필요하므로 총 N명이 반드시 필요하다.
ans = n;
// (2) 부감독관
// 정수형 나눗셈이므로 나누어 떨어지지 않으면,
// 몫에 1을 더한 값이 응시자들을 모두 감시하기 위해 필요한 부감독관의 수가 된다.
// 하지만 그렇게 하지 않아도, c - 1을 더해주고 나누면
// 나누어 떨어지는 경우, 그렇지 않은 경우 모두 올바르게 답을 구할 수 있다.
for(int i = 0; i < n; i++) {
ans += (llint)((a[i] + c - 1) / c);
}
// long long형이므로 %lld로 출력해준다.
printf("%lld\n", ans);
return 0;
}
피드 구독하기:
글 (Atom)