BOJ 1078

슬랙에서 뒤집음이라는 문제가 언급되길래 봤는데.. 맞은 사람도 거의 없고 채점현황이 거의 다 틀렸습니다, 시간초과로 차있다.

그래도 문제는 간단해 보여서 한 번 도전해봤는데... 그냥 brute force로 다 해봤는데...역시나 틀렸다.
이게 백만까지의 수가 입력으로 주어지는데 검사하려면 백만 넘어서까지 검사를 해봐야 하는데 그러면 시간 제한을 넘을 수 밖에 없다...

음.. 그래서 한 번 내가 직접 출력을 해보았다.. 어쩌다 출력을 할 생각을 했는지... ㅋㅋ 여튼 출력하는데도 느려서 파일입출력으로 쫙 뽑아 보면 좋을텐데...라고 생각했다.
파일입출력 좀 공부좀 하자.. 아 근데 어차피 속도는 똑같으려나..

여튼 그런데 정말 어쩌다 내가 출력할 생각을 했는지 몰라도 정말 신기한 결과, 놀라운 결과가 나왔다...
일단 초반밖에 안 보고 껐는데.. d가 9의 배수인 경우에만 x가 존재할 수 있는 것이다...이게 정말이라면 모든 수에 대해 해당한다면 ... d값이 들어왔을 때 9의 배수가 아니면 바로 -1출력하고..음 근데 내가 다시 해보니... 100전까지는 9의 배수인 경우 x가 존재하는데,
그 이후로는 9의 배수라고 해서 무조건 x가 존재하지는 않는다.
하지만 x가 존재하는 경우는 다 d가 9의 배수일 때 인 것 같다..
다시 봐야겠다...

지금 10000까지 돌려보면서 x가 존재하는 경우만 출력하면서 , 그 i값을 9로 나눈 나머지도 같이 옆에 출력시키는 중이다.. 쿨러가 엄청 돌아간다...
이렇게 보면 10000까지는 ...x가 존재하는 경우는 d가 9의 배수일 때만인지 아닌지 알 수 있을듯..

일단은 다 0이다... 10000까지는 d가 9의 배수여야만 x가 존재하는 것 같은데...
그렇다면 9의 배수가 아닌 경우는 -1을 출력해주고
9의 배수가 들어오면 검사를 해보면 되려나... 근데 검사 범위를 어디까지 해야할지..
입력 최대값은 백만인데 백만이 나오려면 x값 후보를 어디까지 검사해야할까..
일단 백만은 9의 배수가 아니니까 한번 구십구만구천...이거로 실험해봐야지.. 그런데 그런다고 알 수 있는 것도 아닌데...

시간이 너무 오래 걸린다...
...음 일단 다음에 풀자...
휴...

BOJ 11966

이 문제는 가볍게 풀 수 있는 쉬운 문제인데...
음 얼마나 간단히 풀 수 있냐...를 보니..
functionx님의 코드를 보니.. 와 2의 제곱의 비트의 특징을 가지고 매우 간단하게 푸셨다...
대단하다...

Codeforces div2 첫 참가 후기

오늘 새벽에 1시 35분부터대략 3시정도까지 Codeforces round #348 div2 edition에 참가했다. 저번에 한 번 메일이 와서 education round 12에 참가한 적은 있었는데, 그것은 rating에 반영이 안되는 연습(?)같은 라운드 였고, rating에도 반영되고 정식적인 div2에 참가한 것은 이번이 처음이다.

나도 rating좀 올리고 red가 되고 싶어서... (일단 10등 안에 드는 것이 목표.. 1년이내로..)
그리고 영어 실력도 늘릴 겸... 그리고 공부좀 더 하고, 실력 좀 더 늘리고 ...이렇게 계속 미루다가는 codeforces에 참가 하지 못할 것 같아서 이번에 참가했다.

새벽 1시 35분부터 시작해서 2시간짜리라... 내 생활리듬이랑 좀 안맞긴 하지만.. 그래도 했다. 음 고작 몇시간 지났다고 잘 기억이 안나는데, 일단 A, B번은 문제 이해도 됐고, 그리 어렵지 않게 풀었던 것 같다. 근데 C번이 이해가 안되고....(영어 공부좀 해야할 듯...) D번은 이해는 했는데... 도저히 문제 제한 시간이 2초안에 끝낼 그런 풀이가 떠오르지 않아서 그냥 냈는데.. 역시나 Time Limit Exceeded.. TLE...ㅠㅠ

그때쯤이 3시인 것 같았는데.. 시간도 얼마 없고, 지금 안자면 다음날 공부도 못할 것 같고 해서 그냥 잤다...

그리고 결과를 봤는데 오 레이팅이 1400이 넘어있었다. 그리고 아이디도 하늘색으로 변해있고...rating 1446!!!

이게 보니까 떨어진 사람도 있고 나 역시 1500에서 1446으로 떨어진 것으로 되어있었다.
음 이게 첫 시작하는 사람에게 일정 rating을 주고 시작하는 것 같은데.. 이제 떨어지지 않도록 공부 열심히 해야겠다.

그리고 나도 문제 다 풀고 다른 사람 코드 에러 찾는 hacking같은 것도 할 여유? 실력이 되도록 열심히 해야겠다!

BOJ 1520

아 진짜 글쓰기 귀찮네... 분명 나중에 까먹을게 뻔해서 이렇게라도 적어놓아야 되는데... 진짜 귀찮다...

그래도 계속 쓰다보면 나아지겠지...
이 내리막길이라는 문제는 처음에 bfs로 접근했다가 메모리 초과가 났는데, bfs외에는 떠오르지가 않아서 계속 bfs로 하다가 결국 포기했었다. 그래서 이번에 풀이를 다시 보고 dp로 접근하려고 했는데, 이제는 풀이가 잘 이해가 안되는 것이었다...

풀이에서는 d[i][j]를 (i, j)에서 (m, n)까지 가는 내리막길 방법의 수로 정의했다.
음 나는 d[i][j]를 (0, 0)에서 (i, j)까지 가는 방법의 수라고 생각했기 때문에 왜 저렇게 해야되는지 이해가 안되었는데... 계속 생각해보니...
중요한 건 저 정의들이 아니라 재귀로 푸냐 아니냐 인 것 같다.

이 문제는 for문을 이용한 dp로 풀기가 매우 어렵다고 한다..(가능은 한건가??) 여튼 내 생각에는 가능한지도 모르겠는데... 일단 내 생각으로는 for문으로 할 경우, 어디서 부터, 즉 어떤 순서로 d[i][j]를 채워나가야 할지 알기가 힘들다는 것이다. 보통 dp에서는 d[i][j]를 채우면 그것을 그대로 쓰는데, for문으로 해서 작은 것부터 채워나가면 이게 또 갱신될 수도 있고, 갱신되기 전의 값을 사용해서 잘못된 값이 구해질 수도 있고... 복잡하다...

하지만 재귀를 쓰면 달라진다. 편하다.

여튼 이 문제는 별거 아닌 것 같지만 정말 좋은 문제 같다.

그래서 일단 내 생각대로 재귀를 만들어서 제출했더니 맞았다.
이제 백준님의 풀이대로 한번 해보려고 한다.

BOJ 1261

알고스팟이라는 문제인데... 음 처음에는 그냥 bfs로 다 탐색하면서 벽을 뚫을 때마다 벽을 뚫은 개수를 d[i][j]에 기록하면서 나가면서, 더 적게 뚫은 경우가 있으면 update해주고 큐에 넣는 식으로 풀었는데, 4ms라는 시간이 나왔다.

다른 분들을 보니 0ms에 푼 분들도 많았다. 그래서 백준님의 풀이 설명을 보니 큐를 2개 이용하거나 덱을 써서 벽이 없는 부분으로만 갈 수 있는 경로와와 벽을 하나 뚫고 갈 수 있는 경로로 나눠서 단계별로 bfs를 실행 시켰고, 그렇게 단계별로 실행함으로 인해, 내가 원래 풀었던 방식에서 있었던 중복된 방문과 update가 없어도 되는 것 같다. 한번 씩만 방문하게 되어 더 시간이 절약되고...

덱을 사용해서 내가 다시 풀어봤는데.. 정말 덱을 이렇게 쓸 수 있다니... 감탄이 나왔다. 덱이 처음에는 별 사용도 안될 필요없는 자료구조인 줄 알았는데 오늘 알고스팟 문제를 풀면서 덱의 멋짐, 아름다움을 느꼈다...
그리고 이 덱을 사용한다는 풀이를 하는 분들도 정말 대단하신 것 같다.

여튼 그래서 0ms에 풀었다. 근데 아직 이해가 안되는 것은 복잡도가 O(n^2)이 나온다는 것인데, 이것이 무엇을 뜻하는지 잘 모르겠다. 한번 메일로 질문해볼까 생각중이다.
-> 백준님게 답장이 왔는데, O(nm)을 뜻하는 거라고 하신다. 내 추측이 맞은 것 같다.